| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1318554 | g31nius | Easter Eggs (info1cup17_eastereggs) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int cnt, ap[1009], i, n, x, q, y;
vector <int> v[1009];
int query ( vector <int> h ) {
cnt++;
if ( h.empty() ) {
return 0;
}
for ( 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 ( i = 1; i <= n; i++ ) {
if ( ap[i] == 1 ) {
return -1;
}
}
for ( auto it: h ) {
if ( it == x ) {
return 1;
}
}
return 0;
}
int findEgg ( int n, vector < pair <int, int> > bridges ) {
if ( query ( {1} ) == 1 ) {
return 1;
}
return 0;
}
int main()
{
vector < pair <int, int> > param;
q = 0;
cin >> n;
for ( i = 1; i < n; i++ ) {
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
param.push_back ( { x,y } );
}
cin >> q;
while ( q > 0 ) {
cin >> x;
cnt = 0;
y = findEgg ( n, param );
if ( x != y ) {
cout << "WA\n";
}
else {
cout << "OK " << cnt << '\n';
}
q--;
}
return 0;
}