//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'
int n;
int dsu[101];
vector<int> cs;
vector<arr(2)> sgs[10];
vector<int> dsuset[101];
void init(){
fill(&dsu[0] , &dsu[n + 1] , -1);
for(int i = 1 ; i <= n ; i++) cs.pb(i) , dsuset[i].pb(i);
}
int findDsu(int v){
if(dsu[v] == -1) return v;
return (dsu[v] = findDsu(dsu[v]));
}
void uDsu(int a , int b){
a = findDsu(a) , b = findDsu(b);
if((int)dsuset[a].size() < (int)dsuset[b].size()) swap(a , b);
int inx = int(lb(cs.bg() , cs.end() , b) - cs.bg());
for(int i = inx ; i < (int)cs.size() - 1 ; i++) cs[i + 1] = cs[i];
cs.pp();
dsu[b] = a;
for(int v : dsuset[b]) dsuset[a].pb(v);
}
int getSet(){
int sz[2];
for(int i = 0 ; i < 10 ; i++){
sz[0] = 0 , sz[1] = 0;
for(int sg = 0 ; sg < (int)sgs[i].size() ; sg++){
for(int v = sgs[i][sg][0] ; v <= sgs[i][sg][1] ; v++){
sz[(sg & 1)] += (int)dsuset[cs[v]].size();
}
}
int a[sz[0]] , b[sz[1]];
int cnt1 = 0 , cnt2 = 0;
for(int sg = 0 ; sg < (int)sgs[i].size() ; sg++){
for(int v = sgs[i][sg][0] ; v <= sgs[i][sg][1] ; v++){
for(int u : dsuset[cs[v]]){
if((sg & 1)) b[cnt2++] = u;
else a[cnt1++] = u;
}
}
}
int d = query(sz[0] , sz[1] , a , b);
if(d == 1) return i;
}
}
arr(2) f(){
for(int i = 0 ; i < 10 ; i++) sgs[i].cl();
int c = (((int)cs.size() - 2) >> 1);
sgs[0].pb({0 , c}) , sgs[0].pb({c + 1 , (int)cs.size() - 1});
for(int i = 0 ; i < 9 ; i++){
for(auto sg : sgs[i]){
if(sg[0] == sg[1]) sgs[i + 1].pb({sg[0] , sg[1]});
else{
c = (sg[0] + sg[1] - 1) >> 1;
sgs[i + 1].pb({sg[0] , c}) , sgs[i + 1].pb({c + 1 , sg[1]});
}
}
}
int inx = getSet();
vector<int> a , b;
for(int sg = 0 ; sg < (int)sgs[inx].size() ; sg++){
for(int v = sgs[inx][sg][0] ; v <= sgs[inx][sg][1] ; v++){
for(int u : dsuset[cs[v]]){
if((sg & 1)) b.pb(u);
else a.pb(u);
}
}
}
int l = 0 , r = (int)a.size() - 1;
while(r > l){
int c = (l + r - 1) >> 1;
int sz[2] = {c - l + 1 , (int)b.size()};
int aa[sz[0]] , bb[sz[1]];
for(int i = 0 ; i < sz[1] ; i++) bb[i] = b[i];
for(int i = 0 ; i < sz[0] ; i++) aa[i] = a[l + i];
int d = query(sz[0] , sz[1] , aa , bb);
if(d == 1) r = c;
else l = c + 1;
}
int ans1 = l;
l = 0 , r = (int)b.size() - 1;
while(r > l){
int c = (l + r - 1) >> 1;
int sz[2] = {1 , c - l + 1};
int aa[sz[0]] , bb[sz[1]];
for(int i = 0 ; i < sz[1] ; i++) bb[i] = b[l + i];
aa[0] = a[ans1];
int d = query(sz[0] , sz[1] , aa , bb);
if(d == 1) r = c;
else l = c + 1;
}
return {a[ans1] , b[l]};
}
void run(int N){
n = N;
while(n == 4);
init();
for(int i = 1 ; i < n ; i++){
arr(2) d = f();
setRoad(d[0] , d[1]);
uDsu(d[0] , d[1]);
}
}
Compilation message
icc.cpp: In function 'int getSet()':
icc.cpp:63:1: warning: control reaches end of non-void function [-Wreturn-type]
63 | }
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
4 ms |
860 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
