Submission #1319594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319594		muhammad-mutahir	Easter Eggs (info1cup17_eastereggs)	C++20	10 / 100	2 ms	1196 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 = 10;
	while(t--){
		int f  = 0;
		for(auto i:ord[cur]){
			int x = query(sub[i.se]);
			if(x == 1){
				f = 1;
				cur = i.se;
				break;
			}
		}
		if(!f)break;
	}
	return cur;
	
}

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