제출 #67638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67638		hamzqq9	Easter Eggs (info1cup17_eastereggs)	C++14	0 / 100	4 ms	852 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;
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 solve(int node) {

	//printf("Curnode-->%d\n",node);

	fsubs(node,0);

	glosub=node;

	int cnt=fcnt(node,0);

	//printf("Cnt found-->%d\n",cnt);

	fsubs(cnt,0);

	F[cnt]=1;

	vector<ii> stree;

	for(int i:v[cnt]) {

		if(F[i]) continue ;

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

	}

	sort(all(stree),greater<ii>());

//	for(ii i:stree) printf("node-->%d size-->%d\n",i.nd,i.st);

	if(sz(stree)==1) {

		vector<int> islands;

		islands.pb(cnt);

		int res=query(islands);

		if(res) {

			ans=cnt;

		}
		else {

			ans=stree[0].nd;

		}

		return ;

	}

	ii odd={-1,-1};

	if(sz(stree)&1) {

		odd=stree.back();

		stree.ppb();

	}

	for(int i=0;i+1<sz(stree);i+=2) {

		vector<int> islands;

		dfs(stree[i].nd,cnt,islands);
		dfs(stree[i+1].nd,cnt,islands);

		islands.pb(cnt);

		int res=query(islands);

		if(res) {

			F[cnt]=0;

			for(int j=0;j<sz(stree);j++) {

				if(i!=j && i+1!=j) F[stree[j].nd]=1;

			}

			if(odd.nd!=-1) F[odd.nd]=1;

			solve(cnt);

			return ;

		}

	}

	if(odd.st!=-1) {

		F[cnt]=0;

		for(int i=0;i<sz(stree);i++) F[stree[i].nd]=1;

		solve(cnt);

		return ; 

	}
	else assert(0);

}

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

	for(int i=1;i<=N;i++) v[i].clear();

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

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

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

	}

	solve(1);
	
	return ans;

}

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