제출 #124085

#제출 시각아이디문제언어결과실행 시간메모리
124085eriksuenderhaufICC (CEOI16_icc)C++11
61 / 100
212 ms572 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include "icc.h" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define mem(a,v) memset((a), (v), sizeof (a)) #define enl printf("\n") #define case(t) printf("Case #%d: ", (t)) #define ni(n) scanf("%d", &(n)) #define nl(n) scanf("%I64d", &(n)) #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i]) #define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i]) #define pri(n) printf("%d\n", (n)) #define prl(n) printf("%I64d\n", (n)) #define pii pair<int, int> #define pil pair<int, long long> #define pll pair<long long, long long> #define vii vector<pii> #define vil vector<pil> #define vll vector<pll> #define vi vector<int> #define vl vector<long long> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef cc_hash_table<int,int,hash<int>> ht; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset; const double pi = acos(-1); const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const int MAXN = 1e2 + 5; const double eps = 1e-9; int par[MAXN], sz[MAXN]; vi comp[MAXN]; int qry(int x) { return par[x] == x ? par[x] : qry(par[x]); } void join(int u, int v) { u = qry(u), v = qry(v); if (u == v) return; if (sz[u] > sz[v]) swap(u, v); par[u] = v; comp[v].insert(comp[v].end(), comp[u].begin(), comp[u].end()); } void print(vi cur) { //for (int i: cur) cerr << i << " "; cerr << "\n"; } pii solve(int N) { pii ret; vi cand; for (int i = 1; i <= N; i++) { if (qry(i) != i) continue; cand.pb(i); } vi l, r; int cl = 0, cr = 0, ind = 0; for (; (1<<ind) < (int)cand.size(); ind++) { l.clear(); r.clear(); cl = 0, cr = 0; for (int j = 0; j < (int)cand.size(); j++) { if ((j >> ind) & 1) l.insert(l.end(), comp[cand[j]].begin(), comp[cand[j]].end()), cl++; else r.insert(r.end(), comp[cand[j]].begin(), comp[cand[j]].end()), cr++; } int la[l.size()], ra[r.size()]; copy(l.begin(), l.end(), la); copy(r.begin(), r.end(), ra); int fl = query((int)l.size(),(int)r.size(), la, ra); if (fl == 1) break; } int lo = 0, hi = cl-1, cur = 0; if (hi == lo) hi--; while (lo <= hi) { int mi = (lo+hi) / 2; cur = 0; vi tmp; for (int i = 0; i < (int)cand.size() && cur <= mi; i++) if ((i >> ind) & 1) tmp.insert(tmp.end(), comp[cand[i]].begin(), comp[cand[i]].end()), cur++; int la[tmp.size()], ra[r.size()]; copy(tmp.begin(), tmp.end(), la); copy(r.begin(), r.end(), ra); int fl = query((int)tmp.size(),(int)r.size(), la, ra); if (fl == 1) hi = mi - 1; else lo = mi + 1; } cur = 0; for (int i = 0; i < (int)cand.size() && cur <= lo; i++) if ((i >> ind) & 1) { if (cur == lo) ret.fi = cand[i]; cur++; } lo = 0, hi = cr-1; if (hi == lo) hi--; while (lo <= hi) { int mi = (lo+hi) / 2; cur = 0; vi tmp; for (int i = 0; i < (int)cand.size() && cur <= mi; i++) if (!((i >> ind) & 1)) tmp.insert(tmp.end(), comp[cand[i]].begin(), comp[cand[i]].end()), cur++; int la[l.size()], ra[tmp.size()]; copy(l.begin(), l.end(), la); copy(tmp.begin(), tmp.end(), ra); int fl = query((int)l.size(),(int)tmp.size(), la, ra); if (fl == 1) hi = mi - 1; else lo = mi + 1; } cur = 0; for (int i = 0; i < (int)cand.size() && cur <= lo; i++) if (!((i >> ind) & 1)) { if (cur == lo) ret.se = cand[i]; cur++; } return ret; } void run(int N) { for (int i = 1; i <= N; i++) par[i] = i, sz[i] = 1, comp[i] = {i}; //cerr << "Number of nodes: " << N << "\n"; for (int t = 1; t < N; t++) { //cerr << "Round: " << t << "\n"; int a, b; tie(a, b) = solve(N); pii nx; vi l = comp[a], r = comp[b]; int lo = 0, hi = l.size()-1; if (l.size() == 1) hi--; while (lo <= hi) { int mi = (lo+hi) / 2; vi tmp; for (int i = 0; i <= mi; i++) tmp.pb(l[i]); print(tmp); print(r); int la[tmp.size()], ra[r.size()]; copy(tmp.begin(), tmp.end(), la); copy(r.begin(), r.end(), ra); int fl = query((int)tmp.size(),(int)r.size(), la, ra); if (fl == 1) hi = mi - 1; else lo = mi + 1; } nx.fi = l[lo]; lo = 0, hi = r.size()-1; if (r.size() == 1) hi--; while (lo <= hi) { int mi = (lo+hi) / 2; vi tmp; for (int i = 0; i <= mi; i++) tmp.pb(r[i]); print(l); print(tmp); int la[l.size()], ra[tmp.size()]; copy(l.begin(), l.end(), la); copy(tmp.begin(), tmp.end(), ra); int fl = query((int)l.size(),(int)tmp.size(), la, ra); if (fl == 1) hi = mi - 1; else lo = mi + 1; } nx.se = r[lo]; setRoad(nx.fi, nx.se); join(nx.fi, nx.se); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...