| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 307063 | jungsnow | ICC (CEOI16_icc) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "icc.h"
#define x first
#define y second
using namespace std;
const int N = 101;
typedef pair <int, int> ii;
struct dsu {
int n, p[N], s[N], C;
vector <int> child[N];
dsu() {};
void init(int _n) {
n = _n;
C = n;
for (int i = 1; i <= n; ++i) {
p[i] = i;
s[i] = 1;
child[i].push_back(i);
}
}
int anc(int u) {
return (p[u] == u ? u : p[u] = anc(p[u]));
}
void merge(int u, int v) {
u = anc(u); v = anc(v);
if (u == v) return;
if (s[u] < s[v]) swap(u, v);
p[v] = u;
for (int x : child[v])
child[u].push_back(x);
child[v].clear();
s[u] += s[v];
--C;
return;
}
} d;
//int p[N], q[N];
//bool query(int n, int m, int a[], int b[]) {
// bool ok;
// cout<<"ask\n";
// cout<<"a ";
// for (int i = 0; i < n; ++i)
// cout<<a[i]<<' ';
// cout<<endl;
// cout<<"b ";
// for (int i = 0; i < m; ++i)
// cout<<b[i]<< ' ';
// cout<<endl;
// cin >> ok;
// return ok;
//}
bool ask(vector <int> C, vector <int> D, bool is) {
vector <int> a, b;
if (!is)
a = C; b = D;
else {
for (int u : C) for (int x : d.child[u]) a.push_back(x);
for (int u : D) for (int x : d.child[u]) b.push_back(x);
}
int sza = (int)a.size(), szb = (int)b.size();
int p[sza], q[szb];
for (int i = 0; i < sza; ++i)
p[i] = a[i];
for (int i = 0; i < szb; ++i)
q[i] = b[i];
return query(sza, szb, p, q);
}
vector <int> join(vector <int>& a, vector <int>& b) {
vector <int> c;
for (int u : a) c.push_back(u);
for (int v : b) c.push_back(v);
return c;
}
int c1, c2, u, v, n;
vector <int> a, b, a1, a2, b1, b2;
bool dfs(vector <int> all, bool has, bool is) {
int tot = (int)all.size();
if (tot < 2) return 0;
a.clear();
b.clear();
a1.clear();
a2.clear();
b1.clear();
b2.clear();
bool ok = has;
for (int i = 0; i < tot / 2; ++i)
a.push_back(all[i]);
for (int i = tot / 2; i < tot; ++i)
b.push_back(all[i]);
if (!ok)
ok = ask(a, b, is);
if (!ok) {
if (dfs(a, 0, is)) return 1;
if (dfs(b, 0, is)) return 1;
return 0;
}
if (tot == 2) {
c1 = a[0];
c2 = b[0];
return 1;
}
for (int i = 0; i < a.size() / 2; ++i)
a1.push_back(a[i]);
for (int i = a.size() / 2; i < a.size(); ++i)
a2.push_back(a[i]);
if (a.size() == 1) {
a1 = a;
a2 = a;
}
for (int i = 0; i < b.size() / 2; ++i)
b1.push_back(b[i]);
for (int i = b.size() / 2; i < b.size(); ++i)
b2.push_back(b[i]);
if (b.size() == 1) {
b1 = b;
b2 = b;
}
ok = ask(a1, b1, is);
if (ok) return dfs(join(a1, b1), 1, is);
ok = ask(a2, b2, is);
if (ok) return dfs(join(a2, b2), 1, is);
ok = ask(a1, b2, is);
if (ok) return dfs(join(a1, b2), 1, is);
return dfs(join(a2, b1), 1, is);
}
//void setRoad(int u, int v) {
// cout<<"is "<<u<<' '<<v<<endl<<endl;
//}
void proc() {
a.clear();
for (int i = 1; i <= n; ++i)
if (d.anc(i) == i)
a.push_back(i);
dfs(a, 0, 1);
dfs(join(d.child[c1], d.child[c2]), 1, 0);
setRoad(c1, c2);
d.merge(c1, c2);
return;
}
void run(int n) {
d.init(n);
for (int i = 1; i < n; ++i)
proc();
}
//int main() {
// cin >> n;
// run(n);
//}