Submission #1319669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319669		muhammad-mutahir	Easter Eggs (info1cup17_eastereggs)	C++20	10 / 100	39 ms	1240 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

#define print(l) for(auto i:l) cout<<i<<" ";cout<<endl;
#define input(t,l,n) vector<t>l(n);for(int i = 0;i<n;i++)cin>>l[i];
// #define int long long
#define pb push_back
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define all(l) l.begin(),l.end()
#define pii pair<int,int>
#define fi first
#define se second

vector<vector<int>>adj,sub;
vector<int>pa;
map<int,int>pos;

void dfs(int v,int par){
	sub[v].pb(v);
	
	
	pa[v] = par;
	for(int i:adj[v]){
		if(pos[i])continue;
		if(i == par)continue;
		dfs(i,v);
		for(int j:sub[i]){
			sub[v].pb(j);
		}
	}
}
int findEgg (int N, vector < pair < int, int > > bridges){
	adj.clear();
	sub.clear();
	pa.clear();
	pos.clear();
	
	pa.resize(N+1);
	sub.resize(N+1);
	adj.resize(N+1);
	
	for(auto i:bridges){
		adj[i.fi].pb(i.se);
		adj[i.se].pb(i.fi);
	}
	dfs(1,1);

	int cur = 1;
	int space = sub[1].size();
	int t = 1000;
	while(t--){
		int cnt = 0;
		for(int i:sub[cur]){
			if(i == cur)continue;
			if(sub[i].size() == 1){
				cnt++;
			}
		}
		// cout<<cur<<" "<<space<<endl;
		// print(sub[cur]);
		if(sub[cur].size()-1 == cnt ){
			// cout<<"ex"<<endl;
			vector<int>chi;
			for(int i :sub[cur]){
				if(i == cur){
					continue;
				}
				chi.pb(i);
			}
			int l = 0;
			int r = chi.size();
			int p = -1;
			while(r-l>1){
				int mid = (l+r)/2;
				vector<int>ask;
				for(int i = l;i<mid;i++){
					if(chi[i] == cur)continue;
					ask.pb(chi[i]);
				}
				ask.pb(cur);
				// print(ask);
				int x = query(ask);
				if(ask.size() == 1){
					p = x;
				}
				if(x){
					r = mid;
				}
				else{
					l = mid;
				}
			}
			if(p == -1){
				p = query({cur});
			}
			if(p){
				return cur;
			}
			else{
				return chi[l];
			}
			
		}
		
		vector<vector<int>>ord;
		int df = 1e9;
		int val = -1;
		if(sub[cur].size() == 0)break;
		for(int i:sub[cur]){
			if(i == cur)continue;
			if(abs((int)sub[i].size()-(space-1)/2) <df){
				df = abs((int)sub[i].size()-space/2);
				val = i;
			}

		}
		// cout<<val<<endl;

		if(val == -1)break;
		
		// print(sub[val]);
		int x = query(sub[val]);
		if(x){
			cur = val;
		}
		else{
			for(auto i:sub[val]){
				pos[i] = 1;
			}
		}
		sub.clear();
		sub.resize(N+1);
		dfs(cur,pa[cur]);
		space = sub[cur].size();
	}
	return cur;
	
}

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