| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 444326 | keta_tsimakuridze | ICC (CEOI16_icc) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "icc.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=105,mod=1e9+7;
int fix[N],X,idx,n;
vector<pair<int,int> > edges;
vector<int> x,y,V[N],comp[N];
int solve(vector<int> x, vector<int> y){
int l = 1, r = (int)x.size() - 2, u = x.back();
while(l <= r) {
int mid = (l+r)/2;
int x1[mid+1],y1[y.size()];
for(int i = 0; i<=mid; i++) {
x1[i] = x[i];
}
for(int i = 0; i<y.size(); i++) {
y1[i] = y[i];
}
int f = query(mid+1,y.size(),x1,y1);
if(f) {
r = mid - 1;
u = x[mid];
}
else {
l = mid + 1;
}
}
if(x.size() > 1 && u == x[1]) {
int x1[1],y1[y.size()];
for(int i = 0; i<1; i++) {
x1[i] = x[i];
}
for(int i = 0; i<y.size(); i++) {
y1[i] = y[i];
}
int f = query(1,y.size(),x1,y1);
if(f) u = x[0];
}
return u;
}
void dfs(int u,int cur) {
comp[cur].push_back(u);
fix[u] = 1;
for(int i=0;i<V[u].size();i++) {
if(!fix[V[u][i]]) dfs(V[u][i],cur);
}
}
void in(vector<int> &x,int cur){
for(int i = 0; i<comp[cur].size();i++){
x.push_back(comp[cur][i]);
}
}
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;
idx = 0;
for(int i=1;i<=n;i++) {
if(!fix[i]) {
comp[cur] .clear();
dfs(i,cur++);
}
}
vector<int> x,y;
for(int i=0; i<=log2(cur-1);i++) {
x.clear(); y.clear();
for(int j=0;j<cur;j++) {
if(j & (1<<i)) {
in(x,j);
}
else in(y,j);
}
int x1[x.size()],y1[y.size()];
for(int i = 0; i<x.size(); i++) x1[i] = x[i];
for(int i = 0; i<y.size(); i++) y1[i] = y[i];
if(query(x.size(),y.size(),x1,y1)) break;
}
int u = solve(x,y);
int v = solve(y,x);
setRoad(u,v);
V[u].push_back(v);
V[v].push_back(u);
}
}