| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 46757 | wzy | ICC (CEOI16_icc) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
#define pb push_back
int pai[150] , peso[150];
vector<int> linked[152];
int fd(int x){
return pai[x] == x ? x : pai[x] = fd(pai[x]);
}
void join(int u , int v){
u = fd(u) , v= fd(v);
if(peso[u] > peso[v]) swap(u,v);
pai[u] = v , peso[v] += peso[u] + 1;
for(int j = 0 ; j < linked[u].size() ; j++) linked[v].push_back(linked[u][j]);
linked[u].clear();
}
bool queryL(int a , int b , vector<int> x , vector<int> y){
int xx[150] , yy[150];
for(int i = 0 ; i < a ; i++) xx[i] = x[i];
for(int i = 0 ; i < b ; i++) yy[i] = y[i];
return query(a , b , xx , yy);
}
bool get(vector<int> l , vector<int> r){
if(l.size() == 0 || r.size() == 0) return 0;
bool w = queryL(l.size() , r.size() , l , r);
if(!w){
vector<int> ll , rr;
for(int i = 0 ; i < l.size() ; i++){
if(ll.size() && fd(ll.back()) == fd(l[i])){
ll.pb(l[i]);
}
else if(rr.size() && fd(rr.back()) == fd(l[i])) rr.pb(l[i]);
else{
if(ll.size() < rr.size()) ll.pb(l[i]);
else rr.pb(l[i]);
}
}
bool q = get(ll , rr);
if(!q){
vector<int> lr, rl;
for(int i = 0 ; i < r.size() ; i++){
if(lr.size() && fd(r[i]) == fd(lr.back())){
lr.pb(r[i]);
}
else if(rl.size() && fd(r[i]) == fd(rl.back())) rl.pb(r[i]);
else{
if(lr.size() < rr.size()) lr.pb(r[i]);
else rl.pb(r[i]);
}
}
q = get(lr , rl);
}
return q;
}
else{
int ll = 0 , rr = l.size() - 1;
int ansj = -1;
while(ll<=rr){
int mid = (ll + rr) / 2;
vector<int> opt;
for(int j = 0 ; j <= mid ; j++) opt.pb(l[j]);
bool q = queryL(opt.size() , r.size() , opt, r);
if(q){
rr = mid - 1;
ansj = mid;
}
else ll = mid + 1;
}
ll = 0 , rr = r.size() - 1;
int ansj2 = -1;
while(ll <= rr){
int mid = (ll +rr)/2;
vector<int> opt;
for(int j = 0 ; j <= mid; j++) opt.pb(r[j]);
bool q = query(opt.size() , l.size() , opt, l);
if(q){
rr = mid - 1;
ansj2 = mid;
}
else ll = mid + 1;
}
setRoad(l[ansj] , r[ansj2]);
return true;
}
}
void run(int n){
for(int i = 0 ; i <= n; i++) pai[i] = i , peso[i] = 0 , linked[i].pb(i);
for(int i = 0 ; i < n - 1 ; i++){
set<int> dependencies;
for(int j = 1 ; j <= n; j ++) dependencies.insert(j);
vector<int> l , r;
for(int j = 1 ; j <= n; j++){
if(!dependencies.count(j)) continue;
if(l.size() < r.size()){
for(int w = 0 ; w < linked[fd(j)].size() ; w++){
l.pb(linked[fd(j)][w]);
dependencies.erase(linked[fd(j)][w]);
}
}
else{
for(int w = 0 ; w < linked[fd(j)].size(); w++){
r.pb(linked[fd(j)][w]);
dependencies.erase(linked[fd(j)][w]);
}
}
}
get(l , r);
}
}