oj.uz

Submission #649364

# Submission time Handle Problem Language Result Execution time Memory
649364 2022-10-10T06:11:50 Z dozer Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 24 ms 356 KB 
#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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Number of queries: 4
2 Correct 1 ms 208 KB Number of queries: 4
3 Correct 1 ms 208 KB Number of queries: 4
4 Correct 1 ms 208 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 336 KB Number of queries: 8
2 Correct 13 ms 356 KB Number of queries: 9
3 Correct 24 ms 352 KB Number of queries: 9
4 Correct 20 ms 348 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 356 KB Number of queries: 9
2 Correct 16 ms 336 KB Number of queries: 9
3 Correct 18 ms 352 KB Number of queries: 9
4 Correct 17 ms 356 KB Number of queries: 9