#include <bits/stdc++.h>
//#define DEBUG
#ifndef DEBUG
#include "icc.h"
#endif
using namespace std;
#ifdef DEBUG
int query(int A, int B, int *a, int *b);
void setRoad(int x, int y);
#endif
int f[105];
vector<int> comp, nodes[105];
int F(int x)
{
if(f[x] == x) return x;
return f[x] = F(f[x]);
}
void init(int N)
{
comp.clear();
for(int i = 1; i <= N; i++)
{
nodes[i].clear();
nodes[i].push_back(i);
f[i] = i;
comp.push_back(i);
}
}
void newRoad(int x, int y)
{
setRoad(x, y);
int fx = F(x), fy = F(y);
f[fy] = fx;
for(auto x: nodes[fy]) nodes[fx].push_back(x);
for(int i = 0; i < comp.size(); i++)
if(comp[i] == fy)
{
comp.erase(comp.begin() + i);
return;
}
}
void solve(vector<int> A, vector<int> B)
{
if(A.size() == 1 && B.size() == 1)
{
newRoad(A[0], B[0]);
return;
}
if(A.size() == 1)
{
solve(B, A);
return;
}
int mij = A.size() / 2;
vector<int> X, Y;
for(int i = 0; i < mij; i++) X.push_back(A[i]);
for(int i = mij; i < A.size(); i++) Y.push_back(A[i]);
int q = query(X.size(), B.size(), X.data(), B.data());
if(q) solve(X, B);
else solve(Y, B);
}
int queryComp(vector<int> A, vector<int> B)
{
if(A.size() == 0 || B.size() == 0) return 0;
vector<int> a, b;
for(auto x: A)
for(auto y: nodes[x])
a.push_back(y);
for(auto x: B)
for(auto y: nodes[x])
b.push_back(y);
return query(a.size(), b.size(), a.data(), b.data());
}
void solveComp(vector<int> A, vector<int> B)
{
if(A.size() == 1 && B.size() == 1)
{
solve(nodes[ A[0] ], nodes[ B[0] ]);
return;
}
if(A.size() == 1)
{
solveComp(B, A);
return;
}
int mij = A.size() / 2;
vector<int> X, Y;
for(int i = 0; i < mij; i++) X.push_back(A[i]);
for(int i = mij; i < A.size(); i++) Y.push_back(A[i]);
int q = queryComp(X, B);
if(q) solveComp(X, B);
else solveComp(Y, B);
}
void solveComp2(vector<int> A, vector<int> B)
{
if(A.size() == 1)
{
solve(nodes[ A[0] ], nodes[ B[0] ]);
return;
}
int mij = A.size() / 2;
vector<int> X[2], Y[2];
for(int i = 0; i < mij; i++) X[0].push_back(A[i]), Y[0].push_back(B[i]);
for(int i = mij; i < A.size(); i++) X[1].push_back(A[i]), Y[1].push_back(B[i]);
int q = queryComp(X[0], Y[0]);
if(q) solveComp2(X[0], Y[0]);
else solveComp2(X[1], Y[1]);
}
void findRoad()
{
int msk = 0;
for(int b = 0; (1 << b) < comp.size(); b++)
{
vector<int> B[2];
for(int i = 0; i < comp.size(); i++)
B[ (i >> b) & 1 ].push_back( comp[i] );
int q = queryComp(B[0], B[1]);
if(q) msk |= (1 << b);
}
vector<int> A, B;
for(int i = 0; i < comp.size(); i++)
{
int j = i ^ msk;
if(i < j && j < comp.size())
A.push_back(comp[i]), B.push_back(comp[j]);
}
solveComp2(A, B);
}
void run(int N)
{
init(N);
while( comp.size() > 1 )
findRoad();
}
#ifdef DEBUG
int query(int A, int B, int *a, int *b)
{
cout << "Query:\n";
for(int i = 0; i < A; i++) cout << a[i] << " ";
cout << '\n';
for(int i = 0; i < B; i++) cout << b[i] << " ";
cout << '\n';
int ans = 0;
cin >> ans;
return ans;
}
void setRoad(int x, int y)
{
cerr << "Set Road: " << x << " " << y << '\n';
}
int main()
{
int N;
cin >> N;
run(N);
}
#endif
Compilation message
icc.cpp: In function 'void newRoad(int, int)':
icc.cpp:42:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < comp.size(); i++)
~~^~~~~~~~~~~~~
icc.cpp: In function 'void solve(std::vector<int>, std::vector<int>)':
icc.cpp:66:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = mij; i < A.size(); i++) Y.push_back(A[i]);
~~^~~~~~~~~~
icc.cpp: In function 'void solveComp(std::vector<int>, std::vector<int>)':
icc.cpp:102:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = mij; i < A.size(); i++) Y.push_back(A[i]);
~~^~~~~~~~~~
icc.cpp: In function 'void solveComp2(std::vector<int>, std::vector<int>)':
icc.cpp:120:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = mij; i < A.size(); i++) X[1].push_back(A[i]), Y[1].push_back(B[i]);
~~^~~~~~~~~~
icc.cpp: In function 'void findRoad()':
icc.cpp:130:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int b = 0; (1 << b) < comp.size(); b++)
~~~~~~~~~^~~~~~~~~~~~~
icc.cpp:133:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < comp.size(); i++)
~~^~~~~~~~~~~~~
icc.cpp:140:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < comp.size(); i++)
~~^~~~~~~~~~~~~
icc.cpp:143:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i < j && j < comp.size())
~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
504 KB |
Ok! 110 queries used. |
2 |
Correct |
9 ms |
504 KB |
Ok! 108 queries used. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
48 ms |
676 KB |
Ok! 611 queries used. |
2 |
Correct |
40 ms |
676 KB |
Ok! 501 queries used. |
3 |
Correct |
43 ms |
676 KB |
Ok! 538 queries used. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
140 ms |
788 KB |
Ok! 1515 queries used. |
2 |
Correct |
118 ms |
932 KB |
Ok! 1220 queries used. |
3 |
Correct |
139 ms |
932 KB |
Ok! 1539 queries used. |
4 |
Correct |
147 ms |
932 KB |
Ok! 1509 queries used. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
137 ms |
932 KB |
Ok! 1515 queries used. |
2 |
Correct |
148 ms |
932 KB |
Ok! 1507 queries used. |
3 |
Correct |
138 ms |
932 KB |
Ok! 1488 queries used. |
4 |
Correct |
153 ms |
932 KB |
Ok! 1536 queries used. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
137 ms |
932 KB |
Ok! 1456 queries used. |
2 |
Correct |
138 ms |
1024 KB |
Ok! 1506 queries used. |
3 |
Correct |
130 ms |
1024 KB |
Ok! 1360 queries used. |
4 |
Correct |
139 ms |
1024 KB |
Ok! 1519 queries used. |
5 |
Correct |
141 ms |
1024 KB |
Ok! 1528 queries used. |
6 |
Correct |
141 ms |
1024 KB |
Ok! 1523 queries used. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
134 ms |
1024 KB |
Ok! 1454 queries used. |
2 |
Correct |
131 ms |
1024 KB |
Ok! 1251 queries used. |