#include "bits/stdc++.h"
/* #define ONPC */
#ifndef ONPC
#include "icc.h"
#endif
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;
#define forn(i,n) for(int i = 0; i < n; ++i)
#define forr(i,n) for(int i = n-1; i >= 0; --i)
#define forbe(i,b,e) for(int i = b; i < e; ++i)
#define all(v) (v).begin(),(v).end()
#define sort(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define endl '\n'
#define pb push_back
#define f first
#define s second
const int N = 100;
int p[N];
int cs[N];
int n;
#ifdef ONPC
int query(int size_a, int size_b, int *a, int *b);
void setRoad(int a, int b);
#endif
int getp(int x) { return p[x] = (x == p[x]) ? x : getp(p[x]); }
int uni(int a, int b) { a = getp(a); b = getp(b); p[a] = b; cs[b] += cs[a]; return(a != b); }
int
ask(bool par, vi va, vi vb)
{
forn(i, sz(va)) {
if (getp(va[i]) == va[i] && par) {
forn(j, n) {
if (va[i] == j) continue;
if (getp(j) == va[i]) va.pb(j);
}
}
}
forn(i, sz(vb)) {
if (getp(vb[i]) == vb[i] && par) {
forn(j, n) {
if (vb[i] == j) continue;
if (getp(j) == vb[i]) vb.pb(j);
// if (getp(j) == vb[i]) cout << "SPL " << j << endl;
}
}
}
int sa, sb;
sa = sz(va);
sb = sz(vb);
int a[N];
int b[N];
forn(i, sz(va)) a[i] = va[i] + 1;
forn(i, sz(vb)) b[i] = vb[i] + 1;
return query(sa, sb, a, b);
}
vi conc(vi a, vi b) {
if (sz(a) < sz(b)) swap(a,b);
vi c = a;
for(int x : b) c.pb(x);
return c;
}
struct tr
{
vi vl;
vi vr;
vi a;
int n;
vector<array<int,2>> ps;
tr(vi& _a) {
a = _a;
n = sz(a);
vl.resize(4*n, -1);
vr.resize(4*n, -1);
build(1, 0, n-1, 0);
sort(ps);
reverse(all(ps));
}
void build(int i, int l, int r, int d) {
// cout << i << ' ' << l << ' ' << r << endl;
int mid = (l+r)>>1;
vl[i] = l;
vr[i] = r;
if (l == r) {
ps.pb({d,l});
return;
}
build(i<<1, l, mid, d+1);
build(i<<1|1, mid+1, r, d+1);
}
vi get(int i) {
if (vl[i] == vr[i]) return {a[vl[i]]};
return conc(get(i<<1) , get(i<<1|1));
}
pi getc(int i) {
if (vl[i<<1] == -1 || vl[i<<1|1] == -1) return {-1,-1};
return {i<<1, i<<1|1};
}
};
void
run (int _n)
{
n = _n;
forn(i, n) p[i] = i;
forn(i, n) cs[i] = 1;
forn(j, n-1) {
vi vals;
vi par, oldpar;
vi ka, kb;
vector<array<int, 2>> sbs;
forn(i, n) if (i == getp(i)) vals.pb(i);
forn(i, n) if (i == getp(i)) sbs.pb({cs[i],i});
sort(sbs);
tr x(vals);
par.pb(1);
for (int i = 0; i < sz(sbs); ++i)
x.a[x.ps[i][1]] = sbs[i][1];
// cout << "SZ: " << sz(vals) << endl;
ka = x.get(2);
kb = x.get(3);
// cout << sz(ka) << ' ' << sz(kb) << endl;
int k = ask(1, ka, kb);
while (!k) {
oldpar = par;
par.clear();
ka.clear();
kb.clear();
// cout << "OLDPAR: ";
for(int i : oldpar) {
// cout << i << ' ';
if (x.getc(i<<1).f != -1) par.pb(i<<1);
if (x.getc(i<<1|1).f != -1) par.pb(i<<1|1);
}
// cout << endl;
// cout << "Par: ";
assert(sz(par));
for(int i : par) {
// cout << i << ' ';
// TODO optimize
ka = conc(ka,x.get(i<<1));
kb = conc(kb,x.get(i<<1|1));
}
// cout << endl;
k = ask(1, ka, kb);
}
// cout << "Stuff" << endl;
vi ta, tb;
forn(i, sz(ka)) {
if (getp(ka[i]) == ka[i]) {
forn(j, n) {
if (ka[i] == j) continue;
if (getp(j) == ka[i]) ka.pb(j);
}
}
}
forn(i, sz(kb)) {
if (getp(kb[i]) == kb[i]) {
forn(j, n) {
if (kb[i] == j) continue;
if (getp(j) == kb[i]) kb.pb(j);
}
}
}
ta = ka;
tb = kb;
int l = 0;
int r = sz(tb);
while(l < r-1) {
kb.clear();
int mid = (l+r)>>1;
forbe(i, l, mid) kb.pb(tb[i]);
if (ask(0,ka,kb)) r = mid;
else l = mid;
}
int n1, n2;
n1 = tb[l];
kb = {n1};
l = 0;
r = sz(ka);
while(l < r-1) {
ka.clear();
int mid = (l+r)>>1;
forbe(i, l, mid) ka.pb(ta[i]);
if (ask(0,ka,kb)) r = mid;
else l = mid;
}
n2 = ta[l];
// cout << n1+1 << ' ' << n2+1 << endl;
setRoad(n1+1, n2+1);
uni(n1,n2);
}
// cout << n << endl;
}
#ifdef ONPC
int rp[N];
pi rd[N];
int cnt = 1;
set<pi> edgs;
int rgtp(int x) {return rp[x] = (rp[x] == x) ? x : rp[x]; }
void
setRoad(int a, int b)
{
if (a > b) swap(a,b);
if (a == rd[cnt-1].f +1 && b == rd[cnt-1].s+1) {
cout << "OK\n";
} else {
cout << "NO\n";
exit(1);
}
if (cnt < n-1) {
edgs.insert(rd[cnt]);
// p[rgtp(rd[cnt].f)] = rd[cnt].s;
++cnt;
}
}
int
query(int size_a, int size_b, int *a, int *b)
{
// cout << "1: ";
// forn(i, size_a) cout << a[i] << ' ';
// cout << endl;
// cout << "2: ";
// forn(i, size_b) cout << b[i] << ' ';
// cout << endl;
forn(i, size_a) --a[i];
forn(i, size_b) --b[i];
// cout << 'T' << endl;
forn(i, size_a) assert(a[i]+1 <= n);
forn(i, size_b) assert(b[i]+1 <= n);
forn(i, size_a) assert(a[i]+1 > 0);
forn(i, size_b) assert(b[i]+1 > 0);
forn(i, size_a)
forn(j, size_b)
assert(a[i] != b[j]);
forn(i, size_a) {
forn(j, size_b) {
if (edgs.count({a[i], b[j]}) || edgs.count({b[j], a[i]}))
return 1;
}
}
// cout << 'F' << endl;
// int x;
// cin >> x;
return 0;
}
void
solve() {
int n;
cin >> n;
forn(i,n) rp[i] = i;
forn(i, n-1) cin >> rd[i].f >> rd[i].s;
forn(i, n-1) --rd[i].f, --rd[i].s;
forn(i, n-1) if (rd[i].f > rd[i].s) swap(rd[i].f, rd[i].s);
edgs.insert(rd[0]);
rp[rd[0].f] = rd[0].s;
run(n);
}
int32_t
main(int argc, char** argv) {
if (argc > 1)
freopen(argv[1],"r", stdin);
solve();
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
468 KB |
Ok! 99 queries used. |
| 2 |
Correct |
5 ms |
468 KB |
Ok! 103 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
524 KB |
Ok! 534 queries used. |
| 2 |
Correct |
35 ms |
516 KB |
Ok! 630 queries used. |
| 3 |
Correct |
45 ms |
520 KB |
Ok! 643 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
512 KB |
Ok! 1478 queries used. |
| 2 |
Correct |
128 ms |
500 KB |
Ok! 1509 queries used. |
| 3 |
Correct |
124 ms |
524 KB |
Ok! 1588 queries used. |
| 4 |
Correct |
126 ms |
532 KB |
Ok! 1527 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
556 KB |
Ok! 1561 queries used. |
| 2 |
Correct |
118 ms |
596 KB |
Ok! 1562 queries used. |
| 3 |
Correct |
131 ms |
556 KB |
Ok! 1591 queries used. |
| 4 |
Correct |
118 ms |
556 KB |
Ok! 1520 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
536 KB |
Ok! 1590 queries used. |
| 2 |
Correct |
148 ms |
556 KB |
Ok! 1597 queries used. |
| 3 |
Correct |
133 ms |
552 KB |
Ok! 1590 queries used. |
| 4 |
Correct |
123 ms |
516 KB |
Ok! 1590 queries used. |
| 5 |
Correct |
113 ms |
536 KB |
Ok! 1505 queries used. |
| 6 |
Correct |
133 ms |
544 KB |
Ok! 1568 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
128 ms |
556 KB |
Ok! 1590 queries used. |
| 2 |
Correct |
120 ms |
560 KB |
Ok! 1596 queries used. |
