| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 269722 | egekabas | Easter Eggs (info1cup17_eastereggs) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include "grader.h"
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
/*int query(vector < int > islands){
for(auto u : islands)
cout << u << ' ';
cout << endl;
int ret;
cin >> ret;
return ret;
}*/
vector<int> g[600];
int n, curn;
int ok[600];
int sz[600];
void calcsz(int v, int prt){
sz[v] = 1;
for(auto u : g[v]){
if(u == prt || ok[u] == 0) continue;
calcsz(u, v);
sz[v] += sz[u];
}
}
vector<int> curv, othv;
void get(int v, int prt, vector<int> &curv){
curv.pb(v);
for(auto u : g[v]){
if(u == prt || ok[u] == 0) continue;
get(u, v, curv);
}
}
int dfs(int v, int prt){
vector<pii> child;
child.pb({-1, -1});
for(auto u : g[v])
if(ok[u])
child.pb({sz[u], u});
vector<bitset<60>> bs(child.size());
bs[0][0] = 1;
for(int i = 1; i < child.size(); ++i)
bs[i] = (bs[i-1]|(bs[i-1]<<child[i].ff));
int cur = (curn-1)/2;
if(bs[child.size()-1][cur] == 0){
for(auto u : g[v]){
if(u == prt || ok[u] == 0) continue;
int bef = sz[u];
sz[u] = sz[v];
sz[v] -= bef;
if(dfs(u, v))
return 1;
sz[v] += bef;
sz[u] = bef;
}
return 0;
}
curv.clear(); othv.clear();
curv.pb(v);
othv.pb(v);
for(int i = child.size()-1; i >= 1; --i){
if(cur-child[i].ff >= 0 && bs[i-1][cur-child[i].ff]){
get(child[i].ss, v, curv);
cur -= child[i].ff;
}
else
get(child[i].ss, v, othv);
}
if(query(curv) == 0)
swap(curv, othv);
return 1;
}
int findEgg(int N, vector<pair<int, int>> bridges){
n = N;
for(auto u : bridges){
g[u.ff].pb(u.ss);
g[u.ss].pb(u.ff);
}
for(int i = 1; i <= n; ++i)
curv.pb(i);
while(1){
if(curv.size() == 1) return curv[0];
if(curv.size() == 2){
if(query({curv[0]}))
return curv[0];
return curv[1];
}
curn = curv.size();
for(int i = 1; i <= n; ++i)
ok[i] = 0;
for(auto u : curv)
ok[u] = 1;
int root = curv[0];
calcsz(root, 0);
dfs(root, 0);
}
}
/*int main(){
cout << findEgg(5, {{1, 2}, {1, 3}, {2, 4}, {4, 5}}) << '\n';
}*/