Submission #1319630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319630		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);
		}
		// sub[v]+=sub[i];
	}
}
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--){
		vector<vector<int>>ord;
		int df = 1e9;
		int val = -1;
		if(sub[cur].size() == 0)break;
		// cout<<cur<<" "<<space<<endl;
		// print(sub[cur]);
		
		for(int i:sub[cur]){
			if(i == cur)continue;
			// if(pos[i])continue;
			if(abs((int)sub[i].size()-space/2) <df){
				
				df = abs((int)sub[i].size()-space/2);
				val = i;
			}

		}
		// cout<<cur<<" "<<space<<" "<<val<<" "<<df<<endl;
		if(val == -1)break;
		// print(sub[val]);
		int x = query(sub[val]);
		// cout<<x<<endl;
		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