#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=105;
int n,vis[N];
VI cc[N],g[N];
/*void setRoad(int a,int b) {
// printf("ROAD: %d %d\n",a,b);
g[a].pb(b);
g[b].pb(a);
}*/
void addRoad(int a,int b) {
setRoad(a,b);
g[a].pb(b);
g[b].pb(a);
}
void dfs(int v,int r) {
cc[r].pb(v);
vis[v]=1;
for (int u:g[v]) if (!vis[u]) dfs(u,r);
}
int qquery(VI a,VI b) {
int sza=SZ(a),szb=SZ(b);
int aa[sza],bb[szb];
rep(i,0,sza) aa[i]=a[i];
rep(i,0,szb) bb[i]=b[i];
rep(i,0,sza) assert(aa[i]>=1&&aa[i]<=n);
rep(i,0,sza) assert(bb[i]>=1&&bb[i]<=n);
return query(sza,szb,aa,bb);
}
VI merge(VI x,VI y) {
VI v;
for (int i:x) v.pb(i);
for (int i:y) v.pb(i);
return v;
}
VI gen(VI v) {
VI ret;
for (int i:v) for (int j:cc[i]) ret.pb(j);
return ret;
}
void findRoad(int r0,int r1) {
int x,y;
int l=0,r=SZ(cc[r1])-1;
while (l<=r) {
int mid=l+r>>1;
VI vv;
rep(i,0,mid+1) vv.pb(cc[r1][i]);
if (qquery(cc[r0],vv)) y=cc[r1][mid],r=mid-1;
else l=mid+1;
}
l=0,r=SZ(cc[r0])-1;
while (l<=r) {
int mid=l+r>>1;
VI vv;
rep(i,0,mid+1) vv.pb(cc[r0][i]);
if (qquery(vv,{y})) x=cc[r0][mid],r=mid-1;
else l=mid+1;
}
addRoad(x,y);
}
void rec(VI v) {
if (SZ(v)==2) {
findRoad(v[0],v[1]);
return;
}
assert(SZ(v)>2);
VI vx[3];
rep(i,0,SZ(v)) vx[i%3].pb(v[i]);
int r1=qquery(gen(vx[0]),gen(vx[1]));
if (r1) {
rec(merge(gen(vx[0]),gen(vx[1])));
return;
}
int r2=qquery(gen(vx[0]),gen(vx[2]));
if (r2) {
rec(merge(gen(vx[0]),gen(vx[2])));
return;
}
rec(merge(gen(vx[1]),gen(vx[2])));
}
void run(int n) {
::n=n;
rep(it,1,n) {
rep(i,1,n+1) {
cc[i].clear();
vis[i]=0;
}
VI v;
rep(i,1,n+1) {
if (!vis[i]) {
dfs(i,i);
v.pb(i);
}
}
rec(v);
}
}
Compilation message
icc.cpp: In function 'void findRoad(int, int)':
icc.cpp:74:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
74 | int mid=l+r>>1;
| ~^~
icc.cpp:82:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
82 | int mid=l+r>>1;
| ~^~
icc.cpp:36:9: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
36 | setRoad(a,b);
| ~~~~~~~^~~~~
icc.cpp:71:6: note: 'x' was declared here
71 | int x,y;
| ^
icc.cpp:71:8: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
71 | int x,y;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
852 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
852 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
