#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct dsu{
int c_cnt;
vector<int> p;
vector<vector<int>> c;
dsu(int n): c(n), p(n, -1), c_cnt(n){
for (int i=0; i<n; i++)
c[i].push_back(i);
}
int find(int v){
if (p[v] < 0) return v;
return p[v] = find(p[v]);
}
void merge(int a, int b){
a = find(a), b = find(b);
if (a == b) return;
if (-p[a] < -p[b]) swap(a, b);
p[a] += p[b]; p[b] = a;
c[a].insert(c[a].end(), c[b].begin(), c[b].end());
c[b].clear();
c_cnt--;
}
};
int raw_query(vector<int> l, vector<int> r){
for (int i=0; i<l.size(); i++) l[i]++;
for (int i=0; i<r.size(); i++) r[i]++;
return query(l.size(), r.size(), l.data(), r.data());
}
int cu_query(dsu &g, vector<int> l, vector<int> r){
if (l.size() == 0 || r.size() == 0) return false;
vector<int> left, right;
for (int x: l)
left.insert(left.end(), g.c[x].begin(), g.c[x].end());
for (int x: r)
right.insert(right.end(), g.c[x].begin(), g.c[x].end());
return raw_query(left, right);
}
void distrib(vector<int> c, vector<int> &left, vector<int> &right){
auto mid = c.begin() + c.size()/2;
left.insert(left.end(), c.begin(), mid);
right.insert(right.end(), mid, c.end());
}
vector<vector<int>> solve1(dsu &g){
vector<vector<int>> c(1);
for (int i=0; i<g.p.size(); i++)
if (g.find(i) == i)
c[0].push_back(i);
while (true){
vector<int> left, right;
for (int i=0; i<c.size(); i++)
distrib(c[i], left, right);
if (cu_query(g, left, right)) break;
for (int i=c.size()-1; i>=0; i--){
auto mid = c[i].begin() + c[i].size()/2;
c.emplace_back(mid, c[i].end());
c[i].resize(c[i].size()/2);
}
vector<vector<int>> nc;
for (int i=0; i<c.size(); i++){
if (c[i].size() == 1) continue;
nc.push_back(move(c[i]));
}
c = move(nc);
}
return c;
}
vector<int> solve2(dsu &g, vector<vector<int>> c){
int bl = 0, br=c.size()-1;
while (bl < br){
int bm = (bl+br)>>1;
vector<int> left, right;
for (int i=0; i<=bm; i++)
distrib(c[i], left, right);
if (cu_query(g, left, right))
br = bm;
else bl = bm+1;
}
return c[bl];
}
pair<int, int> solve3(dsu &g, vector<int> left, vector<int> right){
vector<int> l, r;
for (int x: left) l.insert(l.end(), g.c[x].begin(), g.c[x].end());
for (int x: right) r.insert(r.end(), g.c[x].begin(), g.c[x].end());
while (true){
if (l.size() == 1 && r.size() == 1) return {l[0], r[0]};
if (r.size() == 1) swap(l, r);
vector<int> r1, r2;
distrib(r, r1, r2);
if (raw_query(l, r1)) r = r1;
else r = r2;
}
}
void run(int N){
dsu g(N);
for (int i=0; i<N; i++){
vector<vector<int>> c = solve1(g);
vector<int> cbl = solve2(g, c);
auto mid = cbl.begin() + cbl.size()/2;
vector<int> left(cbl.begin(), mid), right(mid, cbl.end());
pair<int, int> result = solve3(g, left, right);
g.merge(result.first, result.second);
setRoad(result.first+1, result.second+1);
}
}
Compilation message
icc.cpp: In constructor 'dsu::dsu(int)':
icc.cpp:9:25: warning: 'dsu::c' will be initialized after [-Wreorder]
9 | vector<vector<int>> c;
| ^
icc.cpp:8:17: warning: 'std::vector<int> dsu::p' [-Wreorder]
8 | vector<int> p;
| ^
icc.cpp:10:5: warning: when initialized here [-Wreorder]
10 | dsu(int n): c(n), p(n, -1), c_cnt(n){
| ^~~
icc.cpp:8:17: warning: 'dsu::p' will be initialized after [-Wreorder]
8 | vector<int> p;
| ^
icc.cpp:7:9: warning: 'int dsu::c_cnt' [-Wreorder]
7 | int c_cnt;
| ^~~~~
icc.cpp:10:5: warning: when initialized here [-Wreorder]
10 | dsu(int n): c(n), p(n, -1), c_cnt(n){
| ^~~
icc.cpp: In function 'int raw_query(std::vector<int>, std::vector<int>)':
icc.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i=0; i<l.size(); i++) l[i]++;
| ~^~~~~~~~~
icc.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i=0; i<r.size(); i++) r[i]++;
| ~^~~~~~~~~
icc.cpp: In function 'std::vector<std::vector<int> > solve1(dsu&)':
icc.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int i=0; i<g.p.size(); i++)
| ~^~~~~~~~~~~
icc.cpp:55:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i=0; i<c.size(); i++)
| ~^~~~~~~~~
icc.cpp:65:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int i=0; i<c.size(); i++){
| ~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
468 KB |
Ok! 100 queries used. |
| 2 |
Correct |
5 ms |
468 KB |
Ok! 101 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
34 ms |
468 KB |
Ok! 533 queries used. |
| 2 |
Correct |
29 ms |
468 KB |
Ok! 487 queries used. |
| 3 |
Correct |
53 ms |
496 KB |
Ok! 551 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
107 ms |
520 KB |
Ok! 1389 queries used. |
| 2 |
Correct |
95 ms |
524 KB |
Ok! 1215 queries used. |
| 3 |
Correct |
105 ms |
520 KB |
Ok! 1508 queries used. |
| 4 |
Correct |
105 ms |
524 KB |
Ok! 1443 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
96 ms |
424 KB |
Ok! 1438 queries used. |
| 2 |
Correct |
99 ms |
532 KB |
Ok! 1445 queries used. |
| 3 |
Correct |
116 ms |
520 KB |
Ok! 1463 queries used. |
| 4 |
Correct |
101 ms |
512 KB |
Ok! 1483 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
102 ms |
520 KB |
Ok! 1449 queries used. |
| 2 |
Correct |
98 ms |
528 KB |
Ok! 1460 queries used. |
| 3 |
Correct |
132 ms |
652 KB |
Ok! 1360 queries used. |
| 4 |
Correct |
103 ms |
520 KB |
Ok! 1497 queries used. |
| 5 |
Correct |
94 ms |
516 KB |
Ok! 1375 queries used. |
| 6 |
Correct |
97 ms |
512 KB |
Ok! 1395 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
114 ms |
520 KB |
Ok! 1460 queries used. |
| 2 |
Correct |
123 ms |
520 KB |
Ok! 1460 queries used. |
