Submission #538680

#	Time	Username	Problem	Language	Result	Execution time	Memory
538680		M_W	Easter Eggs (info1cup17_eastereggs)	C++14	10 / 100	22 ms	592 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
set<int> adj[600];
int dp[600], dif, src = 1, sz = 0;
pair<int, int> best;
vector<int> vv;

int dfs(int a, int p){
	int sm = 1; sz++;
	for(auto x : adj[a]){
		if(x == p) continue;
		sm += dfs(x, a);
	}
	return dp[a] = sm;
}

void find(int a, int p){
	for(auto x : adj[a]){
		if(x == p) continue;
		if(abs(dp[src] - (2 * dp[x])) < abs(dif)){
			dif = dp[src] - (2 * dp[x]);
			if(dif < 0) best = {x, a};
			else best = {a, x};
		}
		find(x, a);
	}
}

void col(int a, int p){
	for(auto x : adj[a]){
		if(x == p) continue;
		col(x, a);
	}
	vv.push_back(a);
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
	for(auto x : bridges){
    	adj[x.first].insert(x.second);
    	adj[x.second].insert(x.first);
	}
    dfs(src, 0);

    while(sz > 1){
    	best = {0, 0}; dif = INT_MAX;
    	find(src, 0);
    	
    	int u = best.first, v = best.second;
    	adj[u].erase(v); adj[v].erase(u);
    	col(u, 0);
    	
    	int res = query(vv);
    	if(res == 0) src = v;
    	else src = u;
    	
    	sz = 0;
    	dfs(src, 0);
    	vv.clear();
	}
    
    return src;
}

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