| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 924432 | Nurislam | Easter Eggs (info1cup17_eastereggs) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "grader.h"
#include "grader.cpp"
using namespace std;
#define pb push_back
int ans = 0;
vector<vector<int> > g;
vector<int> us;
int m, ctr;
int dcnt(int pos, int pre){
int s = 1;
for(auto to:g[pos]){
if(us[to] || to == pre)continue;
s+=dcnt(to, pos);
}
return s;
}
int dct(int pos, int pre){
bool ok = 1;
int s = 1;
for(auto to:g[pos]){
if(us[to] || to == pre)continue;
int sn = 0;
sn = dcnt(to, pos);
if(sn > m/2)ok = 0;
s+=sn;
}
if(s < m/2)ok = 0;
if(ok)ctr = pos;
return s;
}
vector<int> re;
void dfs(int pos, int pre){
re.pb(pos);
for(int to:g[pos]){
if(us[to] || to == pre)continue;
dfs(to, pos);
}
}
void ctrdec(int pos){
m = dcnt(pos, -1);
m = dct(pos, -1);
us[ctr] = 1;
ans = ctr;
for(auto to:g[ctr]){
if(us[to])continue;
re.clear();
dfs(to, -1);
if(query(re) == 0)continue;
ctrdec(to);
}
}
int findEgg (int n, vector < pair < int, int > > way)
{
g.resize(n+1);
us.resize(n+1);
for(int i = 1; i <= n; i++){
us[i] = 0;
g[i].clear();
}
for(auto [u, v]: way){
g[u].pb(v);
g[v].pb(u);
}
ctrdec(1);
return ans;
}