Submission #1319606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319606		muhammad-mutahir	Easter Eggs (info1cup17_eastereggs)	C++20	10 / 100	41 ms	1244 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;

void dfs(int v,int par){
	sub[v].pb(v);
	
	
	pa[v] = par;
	for(int i:adj[v]){
		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();
	
	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);
	vector<vector<pair<int,int>>>ord(N+1);
	for(int i = 1;i<=N;i++){
		for(int j:adj[i]){
			if(j == pa[i])continue;
			ord[i].pb({(int)sub[j].size(),j});
		}
		sort(all(ord[i]));
		reverse(all(ord[i]));
	}
	int cur = 1;
	int t = 1000;
	map<int,int>pos;
	while(t--){
		int f = 0;
		vector<pair<int,int>>nxt;
		for(int i:sub[cur]){
			if(!pos[i] and i != cur)
				nxt.pb({sub[i].size(),i});
		}
		if(nxt.size() == 0){
			break;
		}
		sort(all(nxt));
		int bst = (nxt.size()/2);
		int val = nxt[bst].se;
		int x  =query(sub[val]);
		if(x){
			cur = val;

		} 
		else{
			for(int i:sub[val]){
				pos[i] = 1;
			}

		} 		
	}
	return cur;
	
}

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