Submission #67748

#	Time	Username	Problem	Language	Result	Execution time	Memory
67748		hamzqq9	Easter Eggs (info1cup17_eastereggs)	C++14	0 / 100	4 ms	812 KiB

eastereggs

#include<bits/stdc++.h>
#include "grader.h"
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 1000000000000000000
#define MOD 1000000007
#define MAX 555
#define LOG 22
using namespace std;

int glosub,ans;
bool init;
int tut;
bool dp[MAX];
int sub[MAX],F[MAX];
vector<int> v[MAX];

void dfs(int node,int ata,vector<int>& islands) {

	islands.pb(node);

	for(int i:v[node]) {

		if(i==ata || F[i]) continue ;

		dfs(i,node,islands);

	}

}

int fcnt(int node,int ata) {

	for(int i:v[node]) {

		if(i==ata || F[i]) continue ;

		if(sub[i]>glosub/2) return fcnt(i,node);

	}

	return node;

}

void fsubs(int node,int ata) {

	sub[node]=1;

	for(int i:v[node]) {

		if(i==ata || F[i]) continue ;

		fsubs(i,node);

		sub[node]+=sub[i];

	}

}

void do_dp(vector<ii> now) {

	for(int i=0;i<=glosub;i++) {

		dp[i]=0;

	}

	dp[0]=1;

	for(int i=0;i<sz(now);i++) {

		for(int j=glosub-now[i].st;j>=0;j--) {

			dp[j+now[i].st]|=dp[j];

		}

	}

}

vector<int> find_them(vector<ii> now,int value,int cnt) {

//	cerr<<value<<endl;

	vector<int> res;

	int last=sz(now)-1;

	for(int i=value;i>0;) {

		for(;last>=0;last--) {

			if(i>=now[last].st && dp[i-now[last].st]) {

				i-=now[last].st;

//				cerr<<"GIRDI\n";

//				cerr<<now[last].nd<<endl;

				dfs(now[last].nd,cnt,res);

//				cerr<<"CIKTI\n";

				last--;

				break ;


			}

		}

	}

//	cerr<<"FFFFFF\n";
	return res;

}

void solve(int node) {

	fsubs(node,0);

	glosub=sub[node];

	int cnt=fcnt(node,0);

	fsubs(cnt,0);

	glosub=sub[cnt];

	vector<ii> stree;

//	cerr<<"Cnt is "<<cnt<<endl;

	for(int i:v[cnt]) {

		if(F[i]) continue ;

		stree.pb({sub[i],i});

	}

	sort(all(stree));

	if(sz(stree)==1) {

		vector<int> is;

		is.pb(cnt);

		if(query(is)) {

			ans=cnt;

		}
		else ans=stree[0].nd;

		return ;

	}

	do_dp(stree);

	for(int i=min(glosub-1,glosub/2+1);i>0;i--) {

		if(dp[i]) {

			vector<int> subs=find_them(stree,i,cnt);

			subs.pb(cnt);

	//		cerr<<"TO GO\n";

//			for(auto go:subs) cerr<<go<<' ';

//			cerr<<endl;

			if(query(subs)) {

				for(int go:v[cnt]) {

					if(F[go]) continue ;

					F[go]=1;

				}

				for(int go:subs) {

					F[go]=0;

				}

			}
			else {

				for(int go:subs) {

					F[go]=1;

				}

				F[cnt]=0;

			}

		//	for(int j=1;j<=tut;j++) cerr<<"i is--> "<<j<<" F[i] "<<F[j]<<endl;

			solve(cnt);

			return ;

		}

	}

	ans=cnt;

}

int findEgg (int N, vector < pair < int, int > > bridges) {

	tut=N;

	for(int i=1;i<=N;i++) F[i]=0;

	if(!init) {

		for(int i=0;i<N-1;i++) {

			v[bridges[i].st].pb(bridges[i].nd);
			v[bridges[i].nd].pb(bridges[i].st);

		}
	
		init=true;

	}

	solve(1);
	
	return ans;

}

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