제출 #649364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
649364		dozer	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	24 ms	356 KiB

eastereggs

#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define sp " "
//#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define M 600


vector<int> adj[M];
bitset<M> vis, done;

int query (vector < int > h);

int ask(bitset<M> curr)
{
	vector<int> v;
	for (int i = 0; i < M; i++)
		if (curr[i]) v.pb(i);
	return query(v);
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
	done.set();
	for (int i = 1; i <= N; i++)
		adj[i].clear();
    for (auto i : bridges)
    {
    	int u = i.st, v = i.nd;
    	adj[u].pb(v);
    	adj[v].pb(u);
    }
    int sz = N / 2, last = N;
    while(last > 1)
    {
    	vis.reset();
    	queue<int> q;
    	int sum = 0;
    	q.push(1);
    	while(!q.empty() && sum < sz)
    	{
    		int top = q.front();
    		q.pop();
    		if (vis[top]) continue;
    		vis[top] = 1;
    		sum += done[top];
    		for (auto i : adj[top])
    		{
    			if (vis[i] == 0) q.push(i);
    		}
    	}
    	/*
    	cout<<last<<sp<<sz<<endl;
    	for (int i = 1; i <= N; i++) cout<<vis[i];
    	cout<<endl;
    	*/
    	int res = ask(vis);
    	if (res == 1)
    	{
    		done &= vis;
    		last = sz;
  			sz /= 2;
    	}
    	else
    	{
    		vis.flip();
    		done &= vis;
    		last -= sz;
    		sz = last / 2;
    	}
    	/*
    	for (int i = 1; i <= N; i++) cout<<done[i];
    	cout<<endl<<endl;*/
    }
    for (int i = 1; i <= N; i++)
    	if (done[i]) return i;
    return 0;
}

• Subtask 1: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 20 / 20