Submission #1226622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226622		akqxolotl	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	1 ms	480 KiB

eastereggs

#include "grader.h"
//Segment Tree is a State of Mind
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" is "<<x<<endl;
#define debugl(x) cerr << #x << " is "; for(auto p : x) cerr << p << " "; cerr << endl;
#define debugpl(x) cerr<<#x<<" is ";for(auto p:x)cerr<<p.first<<" "<<p.second<<endl;cerr<<endl;

//#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)(x).size()

//int inf=4e18+5;
int mod=1e9+7;
vi adj[520];
int pre[520];
int unpre[520];
int c=0;

void dfs(int x,int p){
	c++;
	pre[x]=c;
	unpre[c]=x;
	for(int i:adj[x]){
		if(i==p)continue;
		dfs(i,x);
	}
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
	for(int i=0;i<520;i++)adj[i].clear();
	memset(pre,0,sizeof(pre));
	memset(unpre,0,sizeof(unpre));
	c=0;
	for(auto p:bridges){
		adj[p.fi].pb(p.se);
		adj[p.se].pb(p.fi);
	}
	dfs(1,0);
	int l=0,h=N;
	while(l<h-1){
		int m=(l+h)/2;
		vi q;
		for(int i=1;i<=l;i++){
			q.pb(unpre[i]);
		}
		int res=query(q);
		if(res==0)l=m;
		else h=m;
	}
	return unpre[h];
}

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