| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 396679 | Victor | Easter Eggs (info1cup17_eastereggs) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
const int INF = 1000000007;
vi graph[513], vec;
uset<int> cands, chosen;
int take;
void choose(int u, int p) {
if (!take) return;
if (cands.count(u)) {
--take;
chosen.insert(u);
}
trav(v, graph[u]) if (v != p) choose(v, u);
}
bool dfs(int u, int p) {
bool ret = chosen.count(u);
trav(v, graph[u]) if (v != p) ret |= dfs(v, u);
if (ret) vec.pb(u);
return ret;
}
int recurse() {
if (!sz(cands)) return 0;
int root = *cands.begin();
if (sz(cands) == 1) return root;
chosen.clear();
take = sz(cands) >> 1;
choose(root, root);
vec.clear();
dfs(root, root);
int egg = query(vec);
if (!egg) {
uset<int> next;
trav(cand, cands) if (!chosen.count(cand)) next.insert(cand);
chosen = next;
}
cands = chosen;
return recurse();
}
int findEgg(int n, vii edges) {
cands.clear();
fill(graph,graph+n,vi());
trav(edge, edges) {
int u, v;
tie(u, v) = edge;
graph[u].pb(v);
graph[v].pb(u);
}
rep(i, 0, n) cands.insert(i + 1);
return recurse();
}
static int N, X, cntQ;
static vector<int> v[1009];
int query(vector<int> h) {
cntQ++;
int ap[1009];
if (h.empty()) return 0;
for (int i = 1; i <= N; i++)
ap[i] = 0;
for (auto it = h.begin(); it != h.end(); it++)
ap[*it] = 1;
queue<int> cc;
cc.push(h[0]), ap[h[0]] = 2;
while (!cc.empty()) {
int nod = cc.front();
cc.pop();
for (auto it = v[nod].begin(); it != v[nod].end(); it++)
if (ap[*it] == 1)
ap[*it] = 2, cc.push(*it);
}
for (int i = 1; i <= N; i++)
if (ap[i] == 1) return -1;
for (auto it = h.begin(); it != h.end(); it++)
if (*it == X) return 1;
return 0;
}
int main() {
scanf("%d", &N);
int Queries;
vector<pair<int, int> > param;
for (int i = 1; i < N; i++) {
int x, y;
scanf("%d %d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
param.push_back({x, y});
}
scanf("%d", &Queries);
while (Queries--) {
scanf("%d", &X), cntQ = 0;
int Y = findEgg(N, param);
if (X != Y) {
printf("WA %d instead of %d\n", Y, X);
return 0;
}
printf("OK %d\n", cntQ);
}
return 0;
}