제출 #465277

#제출 시각아이디문제언어결과실행 시간메모리
465277MamedovICC (CEOI16_icc)C++17
0 / 100
249 ms488 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #include "icc.h" #define ll long long #define ui unsigned int #define pii pair<int, int> #define pis pair<int, string> #define piii pair<int, pii> #define pb push_back #define f first #define s second #define oo (1ll << 60) using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); struct DSU { vector<int>root; vector<vector<int>>group; DSU(int n) { group.resize(n + 1); root.resize(n + 1); for(int i = 1; i <= n; ++i) { group[i].clear(); group[i].pb(i); root[i] = i; } } void Union(int u, int v) { u = root[u]; v = root[v]; if(group[u].size() < group[v].size()) { swap(u, v); } for(int node : group[v]) { root[node] = u; group[u].pb(node); } group[v].clear(); } }; void solve(int &size_a, int size_b, int a[], int b[]) { if(size_a > 1) { if(query(size_a / 2, size_b, a, b)) { size_a /= 2; }else { int pos = 0; for(int i = size_a / 2; i < size_a; ++i) { a[pos++] = a[i]; } size_a = pos; } solve(size_a, size_b, a, b); } } const int SIZE = 101; int Query(vector<int> &roots_a, vector<int> &roots_b, DSU &dsu, int i, int j, bool found) { int a[SIZE], b[SIZE]; int size_a = 0, size_b = 0; for(int k = i; k <= j; ++k) { int r = roots_a[k]; if(r == 0) continue; for(int node : dsu.group[r]) { a[size_a++] = node; } } for(int k = i; k <= j; ++k) { int r = roots_b[k]; if(r == 0) continue; for(int node : dsu.group[r]) { b[size_b++] = node; } } if(found) { solve(size_a, size_b, a, b); solve(size_b, size_a, b, a); setRoad(a[0], b[0]); dsu.Union(a[0], b[0]); return 1; } else if(query(size_a, size_b, a, b)) { return 1; }else { return 0; } } void solve(int n, DSU &dsu) { vector<int>roots_a, roots_b; int pw = 1; for(int i = 1; i <= n; ++i) { if(dsu.root[i] == i) { if(roots_a.size() <= roots_b.size()) { roots_a.pb(i); }else { roots_b.pb(i); } if(pw < (int)roots_a.size()) pw <<= 1; } } int res = 0; int sza = (int)roots_a.size(); int szb = (int)roots_b.size(); while(sza <= pw) { roots_a.pb(0); ++sza; } while(szb <= pw) { roots_b.pb(0); ++szb; } int jump; for(jump = sza; !res; jump /= 2) { int pos = jump; while(pos < sza) { swap(roots_a[pos], roots_b[pos]); ++pos; if(pos % jump == 0) pos += jump; } res = Query(roots_a, roots_b, dsu, 0, sza - 1, false); } int l = 0, r = sza - 1; int mid; while(r - l + 1 >= 4 * jump) { mid = (l + r) >> 1; if(Query(roots_a, roots_b, dsu, l, mid, false)) { r = mid; }else { l = mid; } } Query(roots_a, roots_b, dsu, l, r, true); } void run(int n) { DSU dsu(n); for(int i = 1; i < n; ++i) { solve(n, dsu); } }
#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...