| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 444273 | keta_tsimakuridze | ICC (CEOI16_icc) | C++14 | 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 "icc.h"
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N=2e5+5,mod=1e9+7;
int comp[N],fix[N],X,idx,n;
vector<pair<int,int> > edges;
vector<int> a,x,y,V[N];
bool query(int n,int m,vector<int> x,vector<int> y) {
int f = 0;
for(int i = 0; i<x.size(); i++) {
if(x[i] == edges[X].f) f++;
if(x[i] == edges[X].s) f++;
}
if(f>1) return 0;
f = 0;
for(int i = 0; i<y.size(); i++) {
if(y[i] == edges[X].f) f++;
if(y[i] == edges[X].s) f++;
}
if(f>1) return 0;
return 1;
}
int solve(){
int l = 0, r = n-1, u;
while(l<=r) {
int mid = (l+r)/2;
vector<int> x,y;
for(int i = 0; i<=mid; i++) {
x.push_back(a[i]);
}
for(int i = mid+1; i<n; i++) {
if(comp[a[i]] != comp[a[mid]]) y.push_back(a[i]);
}
if(!y.size()) {
r = mid - 1;
continue;
}
bool f = query(x.size(),y.size(),x,y);
if(f) {
r = mid - 1;
u = a[mid];
}
else {
l = mid + 1;
}
}
return u;
}
void dfs(int u,int cur) {
idx++;
a.push_back(u);
comp[u] = cur;
fix[u] = 1;
for(int i=0;i<V[u].size();i++) {
if(!fix[V[u][i]]) dfs(V[u][i],cur);
}
}
void run(int m){
n = m;
int lft = n - 1;
X = -1;
while(lft--){
X++;
for(int i=1;i<=n;i++) fix[i] = 0;
int cur = 0;
a.clear();
idx = 0;
for(int i=1;i<=n;i++) {
if(!fix[i]) {
dfs(i,++cur);
}
}
int l = 1, r = n-1,u = 0,v = 0;
u = solve();
reverse(a.begin(),a.end());
v = solve();
V[u].push_back(v);
V[v].push_back(u);
setRoad(u,v);
}
}