제출 #465168

#제출 시각아이디문제언어결과실행 시간메모리
465168MamedovICC (CEOI16_icc)C++17
0 / 100
406 ms844 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(v); } 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 a[SIZE], b[SIZE]; int size_a = 0, size_b = 0; for(int r : roots_a) { for(int node : dsu.group[r]) { a[size_a++] = node; } } for(int r : roots_b) { for(int node : dsu.group[r]) { b[size_b++] = node; } } if(query(size_a, size_b, a, b)) { 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 { return 0; } } void solve(int n, DSU &dsu) { vector<int>roots; for(int i = 1; i <= n; ++i) { if(dsu.root[i] == i) { roots.pb(i); } } vector<int>roots_a, roots_b; int part1 = 1; int res = 0; while(part1 < (int)roots.size() && !res) { //shuffle(roots.begin(), roots.end(), rng); roots_a.clear(); roots_b.clear(); for(int j = 0; j < (int)roots.size(); ++j) { if(j < part1) { roots_a.pb(roots[j]); }else { roots_b.pb(roots[j]); } } res = Query(roots_a, roots_b, dsu); ++part1; } assert(res == 1); } 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...