//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
#define ask count_common_roads
#include "simurgh.h"
int par[501];
vector<pair<int,int>> adj[513];
int ind5[513][513];
int n;
int vis[513];
int find(int no){
if(par[no]==no){
return no;
}
par[no]=find(par[no]);
return par[no];
}
int ca=-1;
vector<int> pp;
vector<int> pp2;
void dfs(int no,int par2=-1){
if(no==ca){
pp2=pp;
}
for(auto j:adj[no]){
if(j.a!=par2){
pp.pb(j.b);
dfs(j.a,no);
pp.pop_back();
}
}
}
vector<int> ans2;
vector<int> ans;
int ask2(vector<pair<int,int>> cur){
/*cout<<11<<endl;
for(auto i:cur){
cout<<i.a<<"::"<<i.b<<endl;
}*/
for(int i=0;i<n;i++){
vis[i]=0;
}
for(auto i:cur){
vis[i.a]=1;
vis[i.b]=1;
}
/* for(auto i:cur){
cout<<i.a<<"::"<<i.b<<endl;
}*/
vector<int> qq;
int xx=0;
for(int i=1;i<n;i++){
if(vis[i]==0){
qq.pb(ind5[0][i]);
if(ans[ind5[0][i]]==1){
xx--;
}
}
}
for(auto i:cur){
qq.pb(ind5[i.a][i.b]);
qq.pb(ind5[0][i.a]);
if(ans[ind5[0][i.a]]==1){
xx--;
}
}
/* for(auto j:qq){
cout<<j<<".";
}
cout<<endl;*/
xx+=ask(qq);
//cout<<xx<<endl<<endl;
return xx;
}
void solve(vector<pair<int,int>> xx,int val2){
if(val2==0){
return;
}
if(xx.size()==1){
if(xx[0].b>xx[0].a+1 and xx[0].a!=0){
ans[ind5[xx[0].a][xx[0].b]]=1;
ans2.pb(ind5[xx[0].a][xx[0].b]);
}
}
else{
vector<pair<int,int>> yy;
vector<pair<int,int>> zz;
for(int i=0;i<xx.size()/2;i++){
yy.pb(xx[i]);
}
for(int i=xx.size()/2;i<xx.size();i++){
zz.pb(xx[i]);
}
int val3=ask2(yy);
solve(yy,val3);
solve(zz,val2-val3);
}
}
vector<int> find_roads(int nnn,vector<int> uu,vector<int> vv) {
int m=uu.size();
n=nnn;
for(int i=0;i<n;i++){
par[i]=i;
}
vector<pair<pair<int,int>,int>> cur;
vector<pair<pair<int,int>,int>> cur2;
for(int i=0;i<m;i++){
if(uu[i]>vv[i]){
swap(uu[i],vv[i]);
}
ind5[uu[i]][vv[i]]=i;
int x=find(uu[i]);
int y=find(vv[i]);
if(uu[i]!=0){
if(abs(uu[i]-vv[i])>1){
continue;
}
}
if(uu[i]==0){
//par[x]=y;
cur.pb({{uu[i],vv[i]},i});
adj[uu[i]].pb({vv[i],i});
adj[vv[i]].pb({uu[i],i});
}
else{
cur2.pb({{uu[i],vv[i]},i});
}
}
//mt19937 rng;
//rng=mt19937(chrono::steady_clock::now().time_since_epoch().count());
int val;
vector<int> ee;
for(auto j:cur){
ee.pb(j.b);
}
val=ask(ee);
for(int i=0;i<m;i++){
if(uu[i]!=0){
if(abs(uu[i]-vv[i])>1){
ans.pb(-2);
continue;
}
}
ans.pb(0);
}
for(auto j:cur2){
ca=j.a.b;
dfs(j.a.a);
int cur=-1;
for(auto i:pp2){
if(ans[i]!=0){
cur=i;
}
}
/* for(auto i:pp2){
cout<<i<<",";
}
cout<<endl;*/
if(cur==-1){
vector<pair<int,int>> xx;
xx.pb({val,j.b});
for(auto i:pp2){
vector<int> ff;
for(auto jj:ee){
if(jj!=i){
ff.pb(jj);
}
}
ff.pb(j.b);
int val2=ask(ff);
xx.pb({val2,i});
}
sort(xx.begin(),xx.end());
for(int i=0;i<xx.size();i++){
if(xx[i].a==xx.back().a-1){
ans[xx[i].b]=1;
}
else{
ans[xx[i].b]=-1;
}
}
/*for(auto j:xx){
cout<<j.a<<"::"<<j.b<<endl;
}
cout<<endl;*/
}
else{
if(true){
vector<int> ff;
for(auto jj:ee){
if(jj!=cur){
ff.pb(jj);
}
}
ff.pb(j.b);
int val2=ask(ff);
int xx=val;
if(ans[cur]==1){
xx--;
}
if(val2==xx){
ans[j.b]=-1;
}
else{
ans[j.b]=1;
}
}
for(auto i:pp2){
if(ans[i]!=0){
continue;
}
vector<int> ff;
for(auto jj:ee){
if(jj!=i){
ff.pb(jj);
}
}
ff.pb(j.b);
int val2=ask(ff);
int xx=val;
if(ans[j.b]==1){
xx+=1;
}
if(val2==xx){
ans[i]=-1;
}
else{
ans[i]=1;
}
}
}
/* for(auto i:ans){
cout<<i<<".";
}
cout<<endl;*/
}
vector<vector<pair<int,int>>> qq;
for(int i=2;i<=256;i*=2){
vector<vector<int>> aa;
vector<vector<int>> bb;
for(int j=0;j<512;j+=i){
vector<int> cc;
for(int k=j;k<j+i;k++){
cc.pb(k);
}
if((j/i)%2==0){
aa.pb(cc);
}
else{
bb.pb(cc);
}
}
for(int j=0;j<i;j++){
for(int k=0;k<bb.size();k++){
vector<int> dd;
for(int ii=1;ii<i;ii++){
dd.pb(bb[k][ii]);
}
dd.pb(bb[k][0]);
bb[k]=dd;
}
vector<pair<int,int>> rr;
for(int k=0;k<aa.size();k++){
for(int l=0;l<aa[k].size();l++){
rr.pb({aa[k][l],bb[k][l]});
}
}
qq.pb(rr);
}
}
for(int i=0;i<m;i++){
if(ans[i]==0){
ans[i]=1;
}
if(ans[i]==1){
ans2.pb(i);
}
/*if(ans[i]==1 or ans[i]==0){
ans2.pb(i);
}*/
//cout<<ans[i]<<":";
}
//cout<<endl;
for(auto j:qq){
vector<pair<int,int>> cur;
for(auto i:j){
if(i.a<n and i.b<n and i.a!=0 and abs(i.b-i.a)!=1){
cur.pb(i);
}
}
if(cur.size()){
/*for(int i=0;i<n;i++){
vis[i]=0;
}
for(auto i:cur){
vis[i.a]=1;
vis[i.b]=1;
}*/
/*for(auto i:cur){
cout<<i.a<<"::"<<i.b<<endl;
}
cout<<endl;*/
// cout<<ask2(cur)<<endl;
solve(cur,ask2(cur));
}
}
// cout<<endl;
// for(int i=0;i<m;i++){
// cout<<ans[i]<<":";
// }
// cout<<endl;
return ans2;
/* shuffle(cur2.begin(),cur2.end(),rng);
for(auto j:cur2){
if(val==n-1){
break;
}
for(int i=0;i<n;i++){
adj[i].clear();
}
for(auto i:cur){
adj[i.a.a].pb({i.a.b,i.b});
adj[i.a.b].pb({i.a.a,i.b});
}
ca=j.a.b;
dfs(j.a.a);
shuffle(pp2.begin(),pp2.end(),rng);
for(auto i:pp2){
vector<int> ff;
for(auto jj:ee){
if(jj!=i){
ff.pb(jj);
}
}
ff.pb(j.b);
int val2=ask(ff);
if(val2<val){
break;
}
if(val2==val){
continue;
}
vector<pair<pair<int,int>,int>> cur3;
for(auto ii:cur){
if(ii.b==i){
continue;
}
cur3.pb(ii);
}
cur3.pb(j);
cur=cur3;
val=val2;
ee=ff;
break;
}
}*/
// return ee;
}
Compilation message
simurgh.cpp: In function 'void solve(std::vector<std::pair<int, int> >, int)':
simurgh.cpp:98:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int i=0;i<xx.size()/2;i++){
| ~^~~~~~~~~~~~
simurgh.cpp:101:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i=xx.size()/2;i<xx.size();i++){
| ~^~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:122:7: warning: unused variable 'x' [-Wunused-variable]
122 | int x=find(uu[i]);
| ^
simurgh.cpp:123:7: warning: unused variable 'y' [-Wunused-variable]
123 | int y=find(vv[i]);
| ^
simurgh.cpp:187:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
187 | for(int i=0;i<xx.size();i++){
| ~^~~~~~~~~~
simurgh.cpp:268:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
268 | for(int k=0;k<bb.size();k++){
| ~^~~~~~~~~~
simurgh.cpp:277:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
277 | for(int k=0;k<aa.size();k++){
| ~^~~~~~~~~~
simurgh.cpp:278:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
278 | for(int l=0;l<aa[k].size();l++){
| ~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
1356 KB |
correct |
| 2 |
Correct |
4 ms |
1356 KB |
correct |
| 3 |
Correct |
4 ms |
1356 KB |
correct |
| 4 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
1356 KB |
correct |
| 2 |
Correct |
4 ms |
1356 KB |
correct |
| 3 |
Correct |
4 ms |
1356 KB |
correct |
| 4 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
1356 KB |
correct |
| 2 |
Correct |
4 ms |
1356 KB |
correct |
| 3 |
Correct |
4 ms |
1356 KB |
correct |
| 4 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
1356 KB |
correct |
| 2 |
Correct |
5 ms |
1356 KB |
correct |
| 3 |
Correct |
88 ms |
4384 KB |
correct |
| 4 |
Correct |
148 ms |
5912 KB |
correct |
| 5 |
Correct |
141 ms |
5884 KB |
correct |
| 6 |
Correct |
170 ms |
5820 KB |
correct |
| 7 |
Correct |
137 ms |
5824 KB |
correct |
| 8 |
Correct |
146 ms |
5868 KB |
correct |
| 9 |
Correct |
140 ms |
5760 KB |
correct |
| 10 |
Correct |
135 ms |
5816 KB |
correct |
| 11 |
Correct |
147 ms |
5916 KB |
correct |
| 12 |
Correct |
153 ms |
5820 KB |
correct |
| 13 |
Correct |
4 ms |
1356 KB |
correct |
| 14 |
Correct |
134 ms |
5820 KB |
correct |
| 15 |
Correct |
137 ms |
5820 KB |
correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
1356 KB |
correct |
| 2 |
Correct |
4 ms |
1356 KB |
correct |
| 3 |
Correct |
4 ms |
1356 KB |
correct |
| 4 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
