| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 30696 |
2017-07-26T06:56:16 Z |
jenkhai |
ICC (CEOI16_icc) |
C++14 |
|
373 ms |
2372 KB |
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
typedef vector<int> vi;
const int MAXN = 110;
struct UnionFind{
vi p, rank;
vector<vi> members;
int N;
UnionFind(int _N) {
N = _N;
p.assign(N+1, 0);
rank.assign(N+1, 0);
members.assign(N+1, vi());
for(int i=1;i<=N;i++) {
p[i] = i;
members[i].push_back(i);
}
}
UnionFind() {}
int root(int u) {
return (p[u]==u)?u:p[u]=root(p[u]);
}
void merge(int i, int j) {
int b = root(i), s = root(j);
if(rank[b] < rank[s]) swap(b, s);
if(rank[b]==rank[s]) rank[b]++;
for(int i=0;i<members[s].size();i++) {
members[b].push_back(members[s][i]);
}
p[s] = b;
}
};
UnionFind UF;
bool check(queue<int> q1, queue<int> q2) {
int size_a=0, size_b=0, a[MAXN], b[MAXN];
while(!q1.empty()) {
int u = q1.front(); q1.pop();
for(int i=0;i<UF.members[u].size();i++) {
a[size_a++] = UF.members[u][i];
//printf("%d ", UF.members[u][i]);
} //printf("\n");
}
//printf("===\n");
while(!q2.empty()) {
int u = q2.front(); q2.pop();
for(int i=0;i<UF.members[u].size();i++) {
b[size_b++] = UF.members[u][i];
//printf("%d ", UF.members[u][i]);
} //printf("\n");
}
return query(size_a, size_b, a, b);
}
pair<int, int> solve3(queue<int> q1, queue<int> q2) {
if(q1.size() == 0 || q2.size() == 0) return make_pair(-1, -1);
bool last_query = (q1.size()==1)&&(q2.size()==1);
stack<int> s1, s2;
int size_a=0, size_b=0, a[MAXN], b[MAXN];
while(!q1.empty()) {
int u = q1.front(); q1.pop();
for(int i=0;i<UF.members[u].size();i++) {
a[size_a++] = UF.members[u][i];
//printf("%d ", UF.members[u][i]);
} //printf("\n");
s1.push(u);
}
//printf("===\n");
while(!q2.empty()) {
int u = q2.front(); q2.pop();
for(int i=0;i<UF.members[u].size();i++) {
b[size_b++] = UF.members[u][i];
//printf("%d ", UF.members[u][i]);
} //printf("\n");
s2.push(u);
}
//case if two representatives left
if(last_query) {
if(query(size_a, size_b, a, b)) return make_pair(s1.top(), s2.top());
else return make_pair(-1, -1);
}
//otherwise recurse
pair<int, int> ret;
if(s1.size() > s2.size()) {
while(!s2.empty()) {
q2.push(s2.top()); s2.pop();
}
int siz = s1.size()/2;
while(s1.size()>siz) {
q1.push(s1.top()); s1.pop();
}
if(check(q1, q2)) return solve3(q1,q2);
q1 = queue<int>();
while(!s1.empty()) {
q1.push(s1.top()); s1.pop();
}
if(check(q1, q2)) return solve3(q1,q2);
} else {
while(!s1.empty()) {
q1.push(s1.top()); s1.pop();
}
int siz = s2.size()/2;
while(s2.size()>siz) {
q2.push(s2.top()); s2.pop();
}
if(check(q1, q2)) return solve3(q1,q2);
q2 = queue<int>();
while(!s2.empty()) {
q2.push(s2.top()); s2.pop();
}
if(check(q1, q2)) return solve3(q1,q2);
}
return make_pair(-1, -1);
}
pair<int, int> solve(queue<int> q1, queue<int> q2) {
//q1 has same size s q2, or 1 bigger than q2
//rebalance queues and build a and b
while(q2.size()>q1.size()) {
q1.push(q2.front()); q2.pop();
}
while(q1.size()>q2.size()+1) {
q2.push(q1.front()); q1.pop();
}
if(q1.size() == 0 || q2.size() == 0) return make_pair(-1, -1);
bool last_query = (q1.size()==1)&&(q2.size()==1);
stack<int> s1, s2;
int size_a=0, size_b=0, a[MAXN], b[MAXN];
//printf("%d %d\n", q1.size(), q2.size());
while(!q1.empty()) {
int u = q1.front(); q1.pop();
for(int i=0;i<UF.members[u].size();i++) {
a[size_a++] = UF.members[u][i];
//printf("%d ", UF.members[u][i]);
} //printf("\n");
s1.push(u);
}
//printf("===\n");
while(!q2.empty()) {
int u = q2.front(); q2.pop();
for(int i=0;i<UF.members[u].size();i++) {
b[size_b++] = UF.members[u][i];
//printf("%d ", UF.members[u][i]);
} //printf("\n");
s2.push(u);
}
//case if two representatives left
if(last_query) {
if(query(size_a, size_b, a, b)) return make_pair(s1.top(), s2.top());
else return make_pair(-1, -1);
}
//otherwise recurse
pair<int, int> ret;
if(query(size_a, size_b, a, b)) { //across
while(!s1.empty()) {
q1.push(s1.top()); s1.pop();
}
while(!s2.empty()) {
q2.push(s2.top()); s2.pop();
}
return solve3(q1, q2);
} else {
while(!s1.empty()) {
q1.push(s1.top()); s1.pop();
}
ret = solve(q1, queue<int>());
if(ret.first != -1) return ret;
while(!s2.empty()) {
q2.push(s2.top()); s2.pop();
}
ret = solve(q2, queue<int>());
if(ret.first != -1) return ret;
}
//printf("===END===\n");
return make_pair(-1, -1);
}
pair<int, int> solve2(queue<int> q1, queue<int> q2) {
if(q1.size() == 0 || q2.size() == 0) return make_pair(-1, -1);
bool last_query = (q1.size()==1)&&(q2.size()==1);
stack<int> s1, s2;
int size_a=0, size_b=0, a[MAXN], b[MAXN];
//printf("%d %d\n", q1.size(), q2.size());
//printf("qq1: ");
while(!q1.empty()) {
int u = q1.front(); q1.pop();
a[size_a++] = u;
//printf("%d ", u);
s1.push(u);
}
//printf("qq2: ");
while(!q2.empty()) {
int u = q2.front(); q2.pop();
b[size_b++] = u;
//printf("%d ", u);
s2.push(u);
}
//printf("\n");
//case if two nodes left
if(last_query) {
if(query(size_a, size_b, a, b)) return make_pair(s1.top(), s2.top());
else return make_pair(-1, -1);
}
//otherwise recurse
pair<int, int> ret;
if(s1.size() > s2.size()) {
while(!s2.empty()) {
q2.push(s2.top()); s2.pop();
}
int siz = s1.size()/2;
while(s1.size()>siz) {
q1.push(s1.top()); s1.pop();
}
ret = solve2(q1, q2);
if(ret.first != -1) return ret;
q1 = queue<int>();
while(!s1.empty()) {
q1.push(s1.top()); s1.pop();
}
ret = solve2(q1, q2);
if(ret.first != -1) return ret;
} else {
while(!s1.empty()) {
q1.push(s1.top()); s1.pop();
}
int siz = s2.size()/2;
while(s2.size()>siz) {
q2.push(s2.top()); s2.pop();
}
ret = solve2(q1, q2);
if(ret.first != -1) return ret;
q2 = queue<int>();
while(!s2.empty()) {
q2.push(s2.top()); s2.pop();
}
ret = solve2(q1, q2);
if(ret.first != -1) return ret;
}
//printf("===END===\n");
return make_pair(-1, -1);
}
bool test(int x, int y) {
int a[] = {x};
int b[] = {y};
return query(1, 1, a, b);
}
int done[150][150];
void print(int N) {
//printf("TRUE EDGES:\n");
for(int i=1;i<=N;i++) {
for(int j=i+1;j<=N;j++) {
if(done[i][j] || done[j][i]) continue;
if(test(i, j)) {
done[i][j] = 1;
done[j][i] = 1;
//printf("%d %d\n", i, j);
setRoad(i, j);
return;
}
}
}
//printf("===THE END===\n");
}
void print2(int N) {
//printf("TRUE EDGES:\n");
for(int i=1;i<=N;i++) {
for(int j=i+1;j<=N;j++) {
if(done[i][j] || done[j][i]) continue;
if(test(i, j)) {
printf("TRUE:%d %d\n", i, j);
return;
}
}
}
//printf("===THE END===\n");
}
void run(int N) {
UF=UnionFind(N);
int times = N-1;
while(times--) {
//print(N);
//continue;
queue<int> q1, q2;
for(int i=1;i<=N;i++) {
if(UF.p[i] == i) {
//printf("%d ", i);
if(q1.size()>q2.size()) q2.push(i);
else q1.push(i);
}
}//printf("\n");
pair<int, int> reps = solve(q1,q2);
queue<int> qq1, qq2;
//printf("qq1: ");
for(int i=0;i<UF.members[reps.first].size();i++) {
qq1.push(UF.members[reps.first][i]);
//printf("%d ", UF.members[reps.first][i]);
} //printf("\n");
//printf("qq2: ");
for(int i=0;i<UF.members[reps.second].size();i++) {
qq2.push(UF.members[reps.second][i]);
//printf("%d ", UF.members[reps.second][i]);
} //printf("\n");
pair<int, int> ans = solve2(qq1, qq2);
UF.merge(reps.first, reps.second);
//printf("%d: reps:%d %d ans:(%d->%d)\n", q1.size()+q2.size(), reps.first, reps.second, ans.first, ans.second);
done[ans.first][ans.second] = 1;
setRoad(ans.first, ans.second);
//printf("===\n");
//print2(N);
}
}
Compilation message
icc.cpp: In member function 'void UnionFind::merge(int, int)':
icc.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<members[s].size();i++) {
^
icc.cpp: In function 'bool check(std::queue<int>, std::queue<int>)':
icc.cpp:42:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<UF.members[u].size();i++) {
^
icc.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<UF.members[u].size();i++) {
^
icc.cpp: In function 'std::pair<int, int> solve3(std::queue<int>, std::queue<int>)':
icc.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<UF.members[u].size();i++) {
^
icc.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<UF.members[u].size();i++) {
^
icc.cpp:97:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(s1.size()>siz) {
^
icc.cpp:113:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(s2.size()>siz) {
^
icc.cpp: In function 'std::pair<int, int> solve(std::queue<int>, std::queue<int>)':
icc.cpp:148:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<UF.members[u].size();i++) {
^
icc.cpp:157:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<UF.members[u].size();i++) {
^
icc.cpp: In function 'std::pair<int, int> solve2(std::queue<int>, std::queue<int>)':
icc.cpp:231:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(s1.size()>siz) {
^
icc.cpp:249:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(s2.size()>siz) {
^
icc.cpp: In function 'void run(int)':
icc.cpp:320:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<UF.members[reps.first].size();i++) {
^
icc.cpp:325:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<UF.members[reps.second].size();i++) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
2360 KB |
Ok! 219 queries used. |
| 2 |
Correct |
13 ms |
2356 KB |
Ok! 209 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
2368 KB |
Ok! 2005 queries used. |
| 2 |
Correct |
159 ms |
2356 KB |
Ok! 2409 queries used. |
| 3 |
Correct |
176 ms |
2356 KB |
Ok! 2453 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
373 ms |
2372 KB |
Number of queries more than 4500 out of 2250 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
336 ms |
2364 KB |
Number of queries more than 4000 out of 2000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
323 ms |
2352 KB |
Number of queries more than 3550 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
273 ms |
2348 KB |
Number of queries more than 3250 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
