test/aoj/2893.onlinedicon.test.cpp

View this file on GitHub
Last update: 2024-10-12 14:04:05+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/2893
Link: View error logs on GitHub Actions

Depends on

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2893
// competitive-verifier: TLE 3
// competitive-verifier: MLE 256
// 非想定解 MLがギリギリ
// cpuのクロック数，GHA が 2.6GHz で AOJ が 4GHz らしいので TL を 4/2.6 倍している
#include <iostream>
#include "src/DataStructure/OnlineDynamicConnectivity.hpp"
using namespace std;
struct Sum {
 using T= long long;
 static T ti() { return 0; }
 static T op(T l, T r) { return l + r; }
};
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M;
 cin >> N >> M;
 int u[M], v[M];
 long long w[M];
 OnlineDynamicConnectivity<Sum> dicon(N);
 for (int i= 0; i < M; ++i) {
  cin >> u[i] >> v[i] >> w[i];
  --u[i], --v[i];
  dicon.link(u[i], v[i]);
  dicon.set(u[i], dicon[u[i]] + w[i]);
  dicon.set(v[i], dicon[v[i]] + w[i]);
 }
 long long min_score= 1ll << 60;
 long long ans_u= 0, ans_v= 0;
 for (int i= 0; i < M; ++i) {
  dicon.cut(u[i], v[i]);
  long long score;
  if (dicon.connected(u[i], v[i])) {
   score= dicon.prod(u[i]) / 2 - w[i];
  } else {
   long long WA= dicon.prod(u[i]);
   long long WB= dicon.prod(v[i]);
   score= abs(WA - WB) / 2;
  }
  if (min_score > score) min_score= score, ans_u= u[i], ans_v= v[i];
  else if (min_score == score) {
   if (ans_u > u[i]) ans_u= u[i], ans_v= v[i];
   else if (ans_u == u[i] && ans_v > v[i]) ans_v= v[i];
  }
  dicon.link(u[i], v[i]);
 }
 cout << ans_u + 1 << " " << ans_v + 1 << '\n';
 return 0;
}

#line 1 "test/aoj/2893.onlinedicon.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2893
// competitive-verifier: TLE 3
// competitive-verifier: MLE 256
// 非想定解 MLがギリギリ
// cpuのクロック数，GHA が 2.6GHz で AOJ が 4GHz らしいので TL を 4/2.6 倍している
#include <iostream>
#line 2 "src/DataStructure/OnlineDynamicConnectivity.hpp"
#include <vector>
#include <unordered_set>
#line 2 "src/DataStructure/EulerTourTree.hpp"
#include <algorithm>
#include <string>
#include <unordered_map>
#include <cstddef>
#include <cstdint>
#line 2 "src/Internal/HAS_CHECK.hpp"
#include <type_traits>
#define MEMBER_MACRO(member, Dummy, name, type1, type2, last) \
 template <class tClass> struct name##member { \
  template <class U, Dummy> static type1 check(U *); \
  static type2 check(...); \
  static tClass *mClass; \
  last; \
 }
#define HAS_CHECK(member, Dummy) MEMBER_MACRO(member, Dummy, has_, std::true_type, std::false_type, static const bool value= decltype(check(mClass))::value)
#define HAS_MEMBER(member) HAS_CHECK(member, int dummy= (&U::member, 0))
#define HAS_TYPE(member) HAS_CHECK(member, class dummy= typename U::member)
#define HOGE_OR(member, name, type2) \
 MEMBER_MACRO(member, class dummy= typename U::member, name, typename U::member, type2, using type= decltype(check(mClass))); \
 template <class tClass> using name##member##_t= typename name##member<tClass>::type
#define NULLPTR_OR(member) HOGE_OR(member, nullptr_or_, std::nullptr_t)
#define MYSELF_OR(member) HOGE_OR(member, myself_or_, tClass)
#line 8 "src/DataStructure/EulerTourTree.hpp"
template <typename M= void, size_t NODE_SIZE= 4'000'000> class EulerTourTree {
 HAS_MEMBER(op);
 HAS_MEMBER(ti);
 HAS_MEMBER(mp);
 HAS_MEMBER(cp);
 HAS_TYPE(T);
 HAS_TYPE(E);
 NULLPTR_OR(T);
 NULLPTR_OR(E);
 template <class L> static constexpr bool monoid_v= std::conjunction_v<has_T<L>, has_op<L>, has_ti<L>>;
 template <class L> static constexpr bool dual_v= std::conjunction_v<has_T<L>, has_E<L>, has_mp<L>, has_cp<L>>;
 using node_id= int;
 using vertex_id= int;
 struct Node_B {
  node_id ch[2], par;
  uint64_t flag;
 };
 template <class D, bool mo, bool du> struct Node_D: Node_B {};
 template <class D> struct Node_D<D, 1, 0>: Node_B {
  typename M::T val= M::ti(), sum= M::ti();
 };
 template <class D> struct Node_D<D, 0, 1>: Node_B {
  typename M::T val;
  typename M::E laz;
  bool laz_flg;
 };
 template <class D> struct Node_D<D, 1, 1>: Node_B {
  typename M::T val= M::ti(), sum= M::ti();
  typename M::E laz;
  bool laz_flg;
 };
 using Node= Node_D<void, monoid_v<M>, dual_v<M>>;
public:
 using T= nullptr_or_T_t<M>;
 using E= nullptr_or_E_t<M>;
private:
 static inline Node *n= new Node[NODE_SIZE];
 static inline node_id ni= 1;
 node_id new_edge(int s, int d, bool hi) {
  int i= ni++, ri= ni++;
  n[i].flag= (uint64_t(s) << 44) | (uint64_t(d) << 24) | hi;
  n[ri].flag= (uint64_t(d) << 44) | (uint64_t(s) << 24);
  return i;
 }
 static void update(node_id i) {
  n[i].flag&= 0xffffffffff00000f;
  n[i].flag|= ((n[i].flag >> 44) == ((n[i].flag >> 24) & 0xfffff)) << 4;
  n[i].flag&= -11ll, n[i].flag|= (n[i].flag << 1) & 0b1111;
  if constexpr (monoid_v<M>) n[i].sum= n[i].val;
  if (n[i].ch[0]) {
   n[i].flag+= (n[n[i].ch[0]].flag & 0xfffff0), n[i].flag|= n[n[i].ch[0]].flag & 0b1010;
   if constexpr (monoid_v<M>) n[i].sum= M::op(n[n[i].ch[0]].sum, n[i].sum);
  }
  if (n[i].ch[1]) {
   n[i].flag+= (n[n[i].ch[1]].flag & 0xfffff0), n[i].flag|= n[n[i].ch[1]].flag & 0b1010;
   if constexpr (monoid_v<M>) n[i].sum= M::op(n[i].sum, n[n[i].ch[1]].sum);
  }
 }
 static inline void map(T &v, E x, int sz) {
  if constexpr (std::is_invocable_r_v<void, decltype(M::mp), T &, E, int>) M::mp(v, x, sz);
  else M::mp(v, x);
 }
 static inline void propagate(node_id i, const E &x) {
  if (n[i].laz_flg) M::cp(n[i].laz, x);
  else n[i].laz= x, n[i].laz_flg= true;
  if ((n[i].flag >> 44) == ((n[i].flag >> 24) & 0xfffff)) map(n[i].val, x, 1);
  if constexpr (monoid_v<M>) map(n[i].sum, x, ((n[i].flag >> 4) & 0xfffff));
 }
 static inline void push(node_id i) {
  if (!n[i].laz_flg) return;
  if (n[i].ch[0]) propagate(n[i].ch[0], n[i].laz);
  if (n[i].ch[1]) propagate(n[i].ch[1], n[i].laz);
  n[i].laz_flg= false;
 }
 static inline int dir(node_id i) { return n[n[i].par].ch[1] == i; }
 static inline void rot(node_id i) {
  node_id p= n[i].par;
  int d= dir(i);
  if ((n[p].ch[d]= n[i].ch[!d])) n[n[p].ch[d]].par= p;
  n[i].ch[!d]= p;
  if ((n[i].par= n[p].par)) n[n[p].par].ch[dir(p)]= i;
  n[p].par= i, update(p);
 }
 static inline void splay(node_id i) {
  if constexpr (dual_v<M>) push(i);
  for (node_id p= n[i].par; p; rot(i), p= n[i].par) {
   node_id pp= n[p].par;
   if constexpr (dual_v<M>) {
    if (pp) push(pp);
    push(p), push(i);
   }
   if (pp) rot(dir(i) == dir(p) ? p : i);
  }
  update(i);
 }
 static inline node_id merge_back(node_id l, node_id r) {
  if (!l) return r;
  if (!r) return l;
  while (n[l].ch[1]) l= n[l].ch[1];
  return splay(l), n[n[r].par= l].ch[1]= r, update(l), l;
 }
 static inline std::pair<node_id, node_id> split(node_id i) {
  splay(i);
  node_id l= n[i].ch[0];
  return n[i].ch[0]= n[l].par= 0, update(i), std::make_pair(l, i);
 }
 static inline void reroot(node_id v) {
  auto p= split(v);
  merge_back(p.second, p.first), splay(v);
 }
 static inline bool same_root(node_id i, node_id j) {
  if (i) splay(i);
  if (j) splay(j);
  while (n[i].par) i= n[i].par;
  while (n[j].par) j= n[j].par;
  return i == j;
 }
 node_id n_st;
 std::unordered_map<uint64_t, node_id> emp;
public:
 EulerTourTree() {}
 EulerTourTree(int N): n_st(ni) {
  ni+= N;
  for (int i= 0; i < N; i++) n[i + n_st].flag= 0x100001000000 * i;
 }
 const T &operator[](vertex_id x) { return get(x); }
 const T &get(vertex_id x) {
  static_assert(monoid_v<M> || dual_v<M>, "\"get\" is not available\n");
  return n[x + n_st].val;
 }
 void set(vertex_id x, T val) {
  static_assert(monoid_v<M> || dual_v<M>, "\"set\" is not available\n");
  splay(x+= n_st), n[x].val= val, update(x);
 }
 bool edge_exist(vertex_id x, vertex_id y) {
  if (x > y) std::swap(x, y);
  return emp.count(((long long)x << 32) | y);
 }
 void link(vertex_id x, vertex_id y, bool hi= true) {
  if (x > y) std::swap(x, y);
  int ei= new_edge(x, y, hi);
  emp.insert(std::make_pair(((long long)x << 32) | y, ei));
  x+= n_st, y+= n_st, reroot(x), reroot(y);
  n[n[x].par= ei].ch[0]= x, n[n[y].par= ei].ch[1]= y;
  update(ei), merge_back(ei, ei + 1);
 }
 void cut(vertex_id x, vertex_id y) {
  if (x > y) std::swap(x, y);
  int ei= emp[((long long)x << 32) | y], rei= ei + 1;
  emp.erase(((long long)x << 32) | y);
  auto [pl, pr]= split(ei);
  node_id left, center, right;
  if (pl && same_root(pl, rei)) {
   auto [ql, qr]= split(rei);
   left= ql, center= n[qr].ch[1], right= n[pr].ch[1], n[center].par= 0;
  } else {
   splay(ei), n[ei= n[ei].ch[1]].par= 0;
   auto [ql, qr]= split(rei);
   splay(pl), left= pl, right= n[qr].ch[1];
  }
  n[right].par= 0, merge_back(left, right);
 }
 bool connected(vertex_id x, vertex_id y) { return same_root(x + n_st, y + n_st); }
 void subedge_set(vertex_id x, bool val) {
  splay(x+= n_st);
  if (val) n[x].flag|= 0b0100;
  else n[x].flag&= -5ll;
  update(x);
 }
 size_t tree_size(vertex_id x) { return splay(x+= n_st), ((n[x].flag >> 4) & 0xfffff); }
 T prod_tree(vertex_id x) {
  static_assert(monoid_v<M>, "\"prod\" is not available\n");
  return splay(x+= n_st), n[x].sum;
 }
 T prod_subtree(vertex_id x, vertex_id par= -1) {
  if (par == -1) return prod_tree(x);
  cut(x, par);
  T ret= prod_tree(x);
  link(x, par);
  return ret;
 }
 void apply_tree(vertex_id x, E v) {
  static_assert(dual_v<M>, "\"apply\" is not available\n");
  splay(x+= n_st), propagate(x, v), push(x);
 }
 void apply_subtree(vertex_id x, vertex_id par, E v) { cut(x, par), apply_tree(x, v), link(x, par); }
 static std::string which_available() {
  std::string ret= "";
  if constexpr (monoid_v<M>) ret+= "\"prod\" ";
  if constexpr (dual_v<M>) ret+= "\"apply\" ";
  return ret;
 }
 template <class Func> void hilevel_edges(vertex_id v, Func f) {
  splay(v+= n_st);
  while (v && (n[v].flag & 0b0010))
   while (1) {
    if (n[v].flag & 0b0001) {
     f((n[v].flag >> 44), ((n[v].flag >> 24) & 0xfffff)), splay(v), n[v].flag&= -2ll, update(v);
     break;
    } else v= n[v].ch[!(n[v].ch[0] && (n[n[v].ch[0]].flag & 0b0010))];
   }
 }
 template <class Func> int subedges(vertex_id v, Func f) {
  splay(v+= n_st);
  while (v && (n[v].flag & 0b1000))
   for (bool loop= true; loop;) {
    if (n[v].flag & 0b0100) {
     if (f(n[v].flag >> 44)) return 1;
     splay(v), loop= false;
    } else v= n[v].ch[!(n[v].ch[0] && (n[n[v].ch[0]].flag & 0b1000))];
   }
  return 0;
 }
};
#line 5 "src/DataStructure/OnlineDynamicConnectivity.hpp"
template <typename M= void, std::size_t NODE_SIZE= 4'000'000> class OnlineDynamicConnectivity {
 using T= typename EulerTourTree<M, NODE_SIZE>::T;
 using E= typename EulerTourTree<M, NODE_SIZE>::E;
 int N;
 std::vector<EulerTourTree<M, NODE_SIZE>> ett;
 std::vector<std::vector<std::unordered_set<int>>> adj;
 void replace(int x, int y, int level) {
  for (int k= 0; k < level; k++) ett[k].cut(x, y);
  for (int k= level, loop= true; k-- && loop;) {
   if (ett[k].tree_size(x) > ett[k].tree_size(y)) std::swap(x, y);
   ett[k].hilevel_edges(x, [&](int s, int d) { ett[k + 1].link(s, d, true); });
   ett[k].subedges(x, [&](int s) {
    for (auto itr= adj[k][s].begin(); itr != adj[k][s].end();) {
     auto d= *itr;
     if (adj[k][s].size() == 1) ett[k].subedge_set(s, 0);
     if (adj[k][d].size() == 1) ett[k].subedge_set(d, 0);
     adj[k][d].erase(s), itr= adj[k][s].erase(itr);
     if (ett[k].connected(s, d)) {
      if (adj[k + 1][s].size() == 0) ett[k + 1].subedge_set(s, 1);
      if (adj[k + 1][d].size() == 0) ett[k + 1].subedge_set(d, 1);
      adj[k + 1][s].insert(d), adj[k + 1][d].insert(s);
     } else {
      for (int kk= k + 1; kk--;) ett[kk].link(s, d, kk == k);
      return loop= false, true;
     }
    }
    return false;
   });
  }
 }
public:
 OnlineDynamicConnectivity(int N): N(N) { ett.emplace_back(N), adj.emplace_back(N); }
 void link(int x, int y) {
  if (ett[0].connected(x, y)) {
   if (adj[0][x].size() == 0) ett[0].subedge_set(x, 1);
   if (adj[0][y].size() == 0) ett[0].subedge_set(y, 1);
   adj[0][x].insert(y), adj[0][y].insert(x);
  } else ett[0].link(x, y, true);
 }
 void cut(int x, int y) {
  int m= ett.size();
  for (int k= 0; k < m; ++k)
   if (adj[k][x].count(y)) {
    adj[k][x].erase(y), adj[k][y].erase(x);
    if (adj[k][x].size() == 0) ett[k].subedge_set(x, 0);
    if (adj[k][y].size() == 0) ett[k].subedge_set(y, 0);
    return;
   }
  for (int k= m; k--;)
   if (ett[k].edge_exist(x, y)) {
    if (k + 1 == m) ett.emplace_back(N), adj.emplace_back(N);
    replace(x, y, k + 1);
   }
 }
 const T &operator[](int x) { return ett[0][x]; }
 const T &get(int x) { return ett[0].get(x); }
 void set(int x, T val) { ett[0].set(x, val); }
 int size(int x) { return ett[0].tree_size(x); }
 T prod(int x) { return ett[0].prod_tree(x); }
 void apply(int x, E v) { return ett[0].apply_tree(x, v); }
 bool connected(int x, int y) { return ett[0].connected(x, y); }
};
#line 8 "test/aoj/2893.onlinedicon.test.cpp"
using namespace std;
struct Sum {
 using T= long long;
 static T ti() { return 0; }
 static T op(T l, T r) { return l + r; }
};
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M;
 cin >> N >> M;
 int u[M], v[M];
 long long w[M];
 OnlineDynamicConnectivity<Sum> dicon(N);
 for (int i= 0; i < M; ++i) {
  cin >> u[i] >> v[i] >> w[i];
  --u[i], --v[i];
  dicon.link(u[i], v[i]);
  dicon.set(u[i], dicon[u[i]] + w[i]);
  dicon.set(v[i], dicon[v[i]] + w[i]);
 }
 long long min_score= 1ll << 60;
 long long ans_u= 0, ans_v= 0;
 for (int i= 0; i < M; ++i) {
  dicon.cut(u[i], v[i]);
  long long score;
  if (dicon.connected(u[i], v[i])) {
   score= dicon.prod(u[i]) / 2 - w[i];
  } else {
   long long WA= dicon.prod(u[i]);
   long long WB= dicon.prod(v[i]);
   score= abs(WA - WB) / 2;
  }
  if (min_score > score) min_score= score, ans_u= u[i], ans_v= v[i];
  else if (min_score == score) {
   if (ans_u > u[i]) ans_u= u[i], ans_v= v[i];
   else if (ans_u == u[i] && ans_v > v[i]) ans_v= v[i];
  }
  dicon.link(u[i], v[i]);
 }
 cout << ans_u + 1 << " " << ans_v + 1 << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_00.in	AC	22 ms	160 MB
g++-13	00_sample_01.in	AC	22 ms	160 MB
g++-13	10_random_small_00.in	AC	22 ms	160 MB
g++-13	10_random_small_01.in	AC	22 ms	160 MB
g++-13	10_random_small_02.in	AC	22 ms	160 MB
g++-13	10_random_small_03.in	AC	22 ms	160 MB
g++-13	10_random_small_04.in	AC	21 ms	160 MB
g++-13	11_random_med_00.in	AC	83 ms	164 MB
g++-13	11_random_med_01.in	AC	124 ms	166 MB
g++-13	11_random_med_02.in	AC	352 ms	177 MB
g++-13	11_random_med_03.in	AC	170 ms	171 MB
g++-13	11_random_med_04.in	AC	149 ms	169 MB
g++-13	12_random_large_00.in	AC	269 ms	173 MB
g++-13	12_random_large_01.in	AC	1518 ms	224 MB
g++-13	12_random_large_02.in	AC	2179 ms	251 MB
g++-13	12_random_large_03.in	AC	2068 ms	253 MB
g++-13	12_random_large_04.in	AC	598 ms	183 MB
g++-13	12_random_large_05.in	AC	2287 ms	253 MB
g++-13	12_random_large_06.in	AC	1368 ms	215 MB
g++-13	12_random_large_07.in	AC	2196 ms	254 MB
g++-13	12_random_large_08.in	AC	576 ms	187 MB
g++-13	12_random_large_09.in	AC	1595 ms	227 MB
g++-13	19_random_max_00.in	MLE	2362 ms	256 MB
g++-13	19_random_max_01.in	AC	2279 ms	256 MB
g++-13	19_random_max_02.in	AC	2170 ms	255 MB
g++-13	19_random_max_03.in	AC	2070 ms	254 MB
g++-13	19_random_max_04.in	AC	2064 ms	249 MB
g++-13	20_scale_free_00.in	AC	36 ms	161 MB
g++-13	20_scale_free_01.in	AC	690 ms	209 MB
g++-13	20_scale_free_02.in	AC	107 ms	173 MB
g++-13	20_scale_free_03.in	AC	437 ms	195 MB
g++-13	20_scale_free_04.in	AC	330 ms	201 MB
g++-13	90_challenge_00.in	AC	557 ms	188 MB
g++-13	90_challenge_01.in	AC	167 ms	170 MB
g++-13	90_challenge_02.in	AC	808 ms	192 MB
g++-13	90_challenge_03.in	AC	915 ms	197 MB
g++-13	90_challenge_04.in	AC	193 ms	170 MB
clang++-18	00_sample_00.in	AC	23 ms	160 MB
clang++-18	00_sample_01.in	AC	23 ms	160 MB
clang++-18	10_random_small_00.in	AC	23 ms	160 MB
clang++-18	10_random_small_01.in	AC	23 ms	160 MB
clang++-18	10_random_small_02.in	AC	22 ms	160 MB
clang++-18	10_random_small_03.in	AC	23 ms	160 MB
clang++-18	10_random_small_04.in	AC	23 ms	160 MB
clang++-18	11_random_med_00.in	AC	87 ms	164 MB
clang++-18	11_random_med_01.in	AC	134 ms	166 MB
clang++-18	11_random_med_02.in	AC	313 ms	177 MB
clang++-18	11_random_med_03.in	AC	177 ms	171 MB
clang++-18	11_random_med_04.in	AC	165 ms	169 MB
clang++-18	12_random_large_00.in	AC	282 ms	173 MB
clang++-18	12_random_large_01.in	AC	1582 ms	224 MB
clang++-18	12_random_large_02.in	AC	2370 ms	251 MB
clang++-18	12_random_large_03.in	AC	2257 ms	253 MB
clang++-18	12_random_large_04.in	AC	683 ms	183 MB
clang++-18	12_random_large_05.in	AC	2420 ms	253 MB
clang++-18	12_random_large_06.in	AC	1417 ms	215 MB
clang++-18	12_random_large_07.in	AC	2256 ms	254 MB
clang++-18	12_random_large_08.in	AC	676 ms	186 MB
clang++-18	12_random_large_09.in	AC	1864 ms	227 MB
clang++-18	19_random_max_00.in	AC	2668 ms	256 MB
clang++-18	19_random_max_01.in	AC	2446 ms	256 MB
clang++-18	19_random_max_02.in	AC	2394 ms	255 MB
clang++-18	19_random_max_03.in	AC	2290 ms	254 MB
clang++-18	19_random_max_04.in	AC	2242 ms	248 MB
clang++-18	20_scale_free_00.in	AC	37 ms	161 MB
clang++-18	20_scale_free_01.in	AC	795 ms	209 MB
clang++-18	20_scale_free_02.in	AC	106 ms	173 MB
clang++-18	20_scale_free_03.in	AC	476 ms	195 MB
clang++-18	20_scale_free_04.in	AC	380 ms	201 MB
clang++-18	90_challenge_00.in	AC	680 ms	188 MB
clang++-18	90_challenge_01.in	AC	174 ms	170 MB
clang++-18	90_challenge_02.in	AC	862 ms	192 MB
clang++-18	90_challenge_03.in	AC	1015 ms	197 MB
clang++-18	90_challenge_04.in	AC	218 ms	170 MB