| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 61482 | tranxuanbach | Easter Eggs (info1cup17_eastereggs) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include"grader.h"
using namespace std;
#define fi first
#define se second
vector <int> adj[N], ans;
const int N = 1e5 + 5;
int n, num, cur, cnt;
bool ck[N], nw[N];
void dfs(int u, int p){
if (cur == num){
return;
}
if (ck[u]){
cur++;
}
ans.push_back(u);
for (int i = 0; i < adj[u].size(); i++){
int v = adj[u][i];
if (v == p){
continue;
}
dfs(v, u);
}
return;
}
int findEgg(int N, vector <pair <int, int> > bridges){
n = N;
for (int i = 1; i <= n; i++){
ck[i] = 1;
}
cnt = n;
for (int i = 1; i <= n; i++){
adj[i].clear();
}
for (int i = 0; i < n - 1; i++){
adj[bridges[i].fi].push_back(bridges[i].se);
adj[bridges[i].se].push_back(bridges[i].fi);
}
while (cnt != 1){
num = (cnt + 1) / 2;
cur = 0;
ans.clear();
dfs(1, 1);
if (query(ans)){
for (int i = 1; i <= n; i++){
nw[i] = 0;
}
for (int i = 0; i < ans.size(); i++){
nw[ans[i]] = ck[ans[i]];
}
for (int i = 1; i <= n; i++){
ck[i] = nw[i];
}
cnt = num;
}
else{
for (int i = 0; i < ans.size(); i++){
ck[ans[i]] = 0;
}
cnt -= num;
}
}
for (int i = 1; i <= n; i++){
if (ck[i]){
return i;
}
}
}