This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* Bismillahir Rahmanir Rahim */
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
const int N = 105;
int n, par[N], mat[N][N];
set<int>comp;
vector<int>nudes[N];
int Find(int at){
return par[at] == at ? at : par[at] = Find(par[at]);
}
void Union(int a, int b){
int x = Find(a);
int y = Find(b);
for(auto u : nudes[y]){
nudes[x].push_back(u);
}
par[y] = x;
comp.erase(y);
}
int fuk[N], tt;
int get(int sa, int sb, int a[], int b[]){
int lo = 0, hi = sb - 1;
while(lo < hi){
int mid = (lo + hi) / 2; tt = 0;
for(int i=lo;i<=mid;i++) fuk[tt] = b[i], ++tt;
if(query(sa, tt, a, fuk)) hi = mid;
else lo = mid + 1;
}
return b[lo];
}
int aa[N], bb[N], cr[N];
int sa, sb, sz;
void run(int _n){
n = _n;
comp.clear();
for(int i=1;i<=n;i++){
par[i] = i;
comp.insert(i);
nudes[i].push_back(i);
}
for(int road = 1; road < n; ++road){
sz = 0;
for(auto u : comp) cr[++sz] = u;
for(int bit = 0; bit <= 7; ++bit){
sa = 0, sb = 0;
for(int i = 1; i <= sz; ++i){
if(i & (1 << bit)) for(auto v : nudes[cr[i]]) aa[sa] = v, ++sa;
else for(auto v : nudes[cr[i]]) bb[sb] = v, ++sb;
}
if(sa == 0 || sb == 0) continue;
if(query(sa, sb, aa, bb)){
int x = get(sa, sb, aa, bb);
int y = get(sb, sa, bb, aa);
Union(x, y);
setRoad(x, y);
break;
}
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |