#include <bits/stdc++.h>
#include "icc.h"
#define DIM 200
using namespace std;
vector <int> L[DIM];
int n,i,x,y,ok,nr_intv,k,k2;
int v[DIM],w[DIM],t[DIM],aux[DIM],viz[DIM];
pair <int,int> intv[DIM];
/*int query (int n, int m, int a[], int b[]){
int ans;
cout<<n<<" ";
for (int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
cout<<m<<" ";
for (int i=0;i<m;i++)
cout<<b[i]<<" ";
cout<<endl;
cin>>ans;
return ans;
}
void setRoad (int x, int y){
L[x].push_back(y);
L[y].push_back(x);
}*/
int get_rad (int x){
int aux = x;
while (t[x] > 0)
x = t[x];
/*while (t[nr] > 0){
int aux = t[nr];
t[nr] = x;
nr = aux;
}*/
return x;
}
void _union (int x, int y){
int radx = get_rad (x), rady = get_rad (y);
if (radx != rady){
if (t[radx] < t[rady]){
t[radx] += t[rady];
t[rady] = radx;
} else {
t[rady] += t[radx];
t[radx] = rady;
}
}
}
inline int cmp (int a, int b){
return get_rad (a) < get_rad (b);
}
void divide1 (int v[], int k, int st, int dr){
if (st == dr || ok)
return;
int mid = (st+dr)>>1;
if (query(mid-st+1,dr-mid,v+st,v+mid+1)){
/// inseamna ca cele doua noduri sunt in intervale diferite
/// acum dau split pe intervalul mid+1...dr
int le = mid+1, ri = dr;
while (le < ri){
int m = (le+ri)>>1;
/// le...m
if (query(mid-st+1,m-le+1,v+st,v+le)){ /// sigur nodul e in stanga
ri = m;
} else le = m+1;
}
y = v[le];
int poz = le;
/// acum trb sa aflu x
le = st, ri = mid;
while (le < ri){
int m = (le+ri)>>1;
/// le...m
if (query(1,m-le+1,v+poz,v+le))
ri = m;
else le = m+1;
}
x = v[le];
ok = 1;
return;
}
divide1 (v,k,st,mid);
divide1 (v,k,mid+1,dr);
}
void divide2 (int v[], int k, int w[], int k2, int st, int dr){
if (!k2 || k < 1)
return;
if (st == dr){
y = v[st];
ok = 1;
return;
}
int mid = (st+dr)>>1;
if (query(k2,mid-st+1,w,v+st))
divide2 (v,k,w,k2,st,mid);
else divide2 (v,k,w,k2,mid+1,dr);
}
void divide3 (int v[], int k, int l, int r, int st, int dr){
if (l == r || st == dr || ok)
return;
int m = (l+r)>>1; /// l,r,m sunt indicii intervalului
int dim1 = intv[m].second-st+1, dim2 = dr-intv[m].second;
if (query(dim1,dim2,v+st,v+intv[m].second+1)){
/// am gasit bucatile, pot sa apuc sa le caut pe fiecare in parte
int p = intv[m+1].first, u = dr;
while (p < u){
int mij = (p+u)>>1;
if (query(dim1,mij-p+1,v+st,v+p))
u = mij;
else p = mij+1;
}
y = v[p];
int poz = p;
/// l am gasit pe y, acum trb sa l caut pe x in celalalt interval
p = st, u = intv[m].second;
while (p < u){
int mij = (p+u)>>1;
if (query(1,mij-p+1,v+poz,v+p))
u = mij;
else p = mij+1;
}
x = v[p];
ok = 1;
return;
}
divide3 (v,k,l,m,st,intv[m].second);
divide3 (v,k,m+1,r,intv[m+1].first,dr);
}
void solve (){
/// vr sa determin muchia x,y
/// cazul 1: x si y nu au mai fost vizitate
k = 0, k2 = 0, ok = 0;
for (int i=1;i<=n;i++){
if (!viz[i])
v[k++] = i;
else w[k2++] = i;
}
if (k > 1){ /// sa am cel putin doua elemente
divide1 (v,k,0,k-1);
if (ok)
return;
}
/// cazul 2: x face parte dintr-o multime si y e nevizitat
divide2 (v,k,w,k2,0,k-1);
if (ok){
/// acum trb sa l caut pe x
aux[0] = y;
int st = 0, dr = k2-1;
while (st < dr){
int mid = (st+dr)>>1;
if (query(1,mid-st+1,aux,w+st))
dr = mid;
else st = mid+1;
}
x = w[st];
return;
}
/// cazul 3: x si y fac parte fiecare dintr o multime
/// sortez nodurile din multimi dupa tata, ca sa am intervale compacte care repr multimile
sort (w,w+k2,cmp);
/// acum principiul e asemanator cu cel de la primul caz
/// obtin intervalele
int val = 0;
nr_intv = 0;
for (int i=0;i<k2-1;i++){
if (get_rad(w[i]) != get_rad(w[i+1])){
intv[++nr_intv] = make_pair(val,i);
val = i+1;
}
}
intv[++nr_intv] = make_pair(val,k2-1);
divide3 (w,k2,1,nr_intv,0,k2-1);
return;
}
void run (int n){
for (i=1;i<n;i++){
solve();
setRoad(x,y);
_union (x,y);
viz[x] = viz[y] = 1;
//cout<<x<<" "<<y<<endl;
}
}
Compilation message
icc.cpp: In function 'int get_rad(int)':
icc.cpp:27:9: warning: unused variable 'aux' [-Wunused-variable]
int aux = x;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
376 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
