#include <stdio.h>
#include "icc.h"
#include <vector>
#include <set>
#include <utility>
#include <stdlib.h>
#include <algorithm>
#define ii std::pair<int,int>
std::vector<int> nd[50000];
int par[300];
int qryA[300];
int qryB[300];
int q1(std::vector<int> &a1, std::vector<int> &a2){
int sa = 0;
int sb = 0;
for(int i: a1){
for(int j:nd[i]){
qryA[sa] = j;
sa++;
};
};
for(int i: a2){
for(int j:nd[i]){
qryB[sb] = j;
sb++;
};
};
if(sa == 0 || sb == 0)return 0;
return query(sa,sb,qryA,qryB);
};
ii findCC(std::vector<int> lf, std::vector<int> rg,int fg){
if(lf.size() == 1 && rg.size() == 1)return {lf[0],rg[0]};
if(fg == 0 && lf.size() == 1)return findCC(lf,rg,1);
std::vector<int> l1,l2;
std::vector<int> r1,r2;
if(fg == 0){
for(int i = 0;i<lf.size();i++){
if(i%2)l2.push_back(lf[i]);
else l1.push_back(lf[i]);
};
if(q1(l1,rg))return findCC(l1,rg,0);
else return findCC(l2,rg,0);
}else{
for(int i = 0;i<rg.size();i++){
if(i%2)r2.push_back(rg[i]);
else r1.push_back(rg[i]);
};
if(q1(lf,r1))return findCC(lf,r1,1);
else return findCC(lf,r2,1);
};
};
ii findC(std::vector<int> akt){
if(akt.size() == 0)return {-1,-1};
if(akt.size() == 1)return {-1,-1};
if(akt.size() == 2){
std::vector<int> t1 = {akt[0]};
std::vector<int> t2 = {akt[1]};
if(q1(t1,t2)){
std::vector<int> l1,r1;
for(auto i: nd[akt[0]])l1.push_back(i);
for(auto i: nd[akt[1]])r1.push_back(i);
return findCC(l1,r1,0);
}else{
return {-1,-1};
};
}else{
std::vector<int> lf;
std::vector<int> rg;
std::vector<int> pos;
for(int i = 0;i<10;i++)pos.push_back(i);
int pp = rand()%pos.size();
int pw = (1<<pos[pp]);
pos.erase(pos.begin() + pp);
while(true){
lf.clear();
rg.clear();
for(int i = 0;i<akt.size();i++){
if(i&pw)lf.push_back(akt[i]);
else rg.push_back(akt[i]);
};
int tmp = q1(lf,rg);
if(tmp)break;
else{
pp = rand()%pos.size();
pw = (1<<pos[pp]);
pos.erase(pos.begin() + pp);
};
};
std::vector<int> l1,r1;
for(auto i: lf)
for(auto j: nd[i])l1.push_back(j);
for(auto i: rg)
for(auto j: nd[i])r1.push_back(j);
return findCC(l1,r1,0);
};
};
void run(int N){
int cn = N+1;
std::vector<int> nodes;
for(int i = 1;i<=N;i++){
nodes.push_back(i);
nd[i].push_back(i);
par[i] = i;
};
for(int g = 0;g<N-1;g++){
ii tmp = findC(nodes);
setRoad(tmp.first,tmp.second);
std::vector<int> ttp;
int p1 = par[tmp.first];
int p2 = par[tmp.second];
for(int i: nodes){
if(i != p1 && i != p2)ttp.push_back(i);
};
for(auto i: nd[p1]){
par[i] = cn;
nd[cn].push_back(i);
};
for(auto i: nd[p2]){
par[i] = cn;
nd[cn].push_back(i);
};
nodes = ttp;
nodes.push_back(cn++);
};
};
/*
int adj[120][120];
std::vector<ii> rd;
int qcnt = 0;
int query(int size_a, int size_b ,int a[], int b[]){
qcnt++;
//printf("query: %d %d\n",size_a,size_b);
//for(int i = 0;i<size_a;i++)printf("%d ",a[i]);
//puts("");
//for(int i = 0;i<size_b;i++)printf("%d ",b[i]);
//puts("");
for(int i = 0;i<size_a;i++){
for(int j = 0;j<size_b;j++){
if(adj[a[i]][b[j]]){
// printf("return 1\n");
return 1;
};
};
};
//printf("return: 0\n");
return 0;
};
int cnt = 0;
int pqcnt = 0;
void setRoad(int a, int b){
printf("SetRoad %d %d %d\n",a,b,qcnt-pqcnt);
pqcnt = qcnt;
if(rd[cnt].first == a && rd[cnt].second == b){
cnt++;
if(cnt == rd.size())return;
adj[rd[cnt].first][rd[cnt].second] = 1;
adj[rd[cnt].second][rd[cnt].first] = 1;
}else if(rd[cnt].first == b && rd[cnt].second == a){
cnt++;
if(cnt == rd.size())return;
adj[rd[cnt].first][rd[cnt].second] = 1;
adj[rd[cnt].second][rd[cnt].first] = 1;
}else{
printf("Error\n");
exit(0);
};
};
int main(void){
int n;
scanf("%d",&n);
int a,b;
for(int i = 0;i<n-1;i++){
scanf("%d %d",&a,&b);
rd.push_back({a,b});
};
adj[rd[cnt].first][rd[cnt].second] = 1;
adj[rd[cnt].second][rd[cnt].first] = 1;
run(n);
printf("nice %d\n",qcnt);
return 0;
};
*/
Compilation message
icc.cpp: In function 'std::pair<int, int> findCC(std::vector<int>, std::vector<int>, int)':
icc.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<lf.size();i++){
~^~~~~~~~~~
icc.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<rg.size();i++){
~^~~~~~~~~~
icc.cpp: In function 'std::pair<int, int> findC(std::vector<int>)':
icc.cpp:82:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<akt.size();i++){
~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
1664 KB |
Ok! 98 queries used. |
| 2 |
Correct |
9 ms |
1664 KB |
Ok! 107 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
40 ms |
1756 KB |
Ok! 543 queries used. |
| 2 |
Correct |
49 ms |
1664 KB |
Ok! 654 queries used. |
| 3 |
Correct |
46 ms |
1664 KB |
Ok! 651 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
138 ms |
1756 KB |
Ok! 1434 queries used. |
| 2 |
Correct |
170 ms |
1760 KB |
Ok! 1599 queries used. |
| 3 |
Correct |
177 ms |
1664 KB |
Ok! 1597 queries used. |
| 4 |
Correct |
139 ms |
1664 KB |
Ok! 1522 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
182 ms |
1764 KB |
Ok! 1548 queries used. |
| 2 |
Correct |
177 ms |
1772 KB |
Ok! 1534 queries used. |
| 3 |
Correct |
149 ms |
1796 KB |
Ok! 1589 queries used. |
| 4 |
Correct |
128 ms |
1756 KB |
Ok! 1495 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
152 ms |
1760 KB |
Ok! 1587 queries used. |
| 2 |
Correct |
155 ms |
1784 KB |
Ok! 1586 queries used. |
| 3 |
Correct |
163 ms |
1756 KB |
Ok! 1624 queries used. |
| 4 |
Correct |
146 ms |
1912 KB |
Ok! 1610 queries used. |
| 5 |
Correct |
142 ms |
1756 KB |
Ok! 1510 queries used. |
| 6 |
Correct |
133 ms |
1764 KB |
Ok! 1563 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
142 ms |
1784 KB |
Ok! 1621 queries used. |
| 2 |
Correct |
199 ms |
1796 KB |
Ok! 1584 queries used. |
