oj.uz

Submission #538680

# Submission time Handle Problem Language Result Execution time Memory
538680 2022-03-17T13:16:39 Z M_W Easter Eggs (info1cup17_eastereggs) C++14
10 / 100
 22 ms 592 KB 
#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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Number of queries: 4
2 Partially correct 1 ms 208 KB Number of queries: 5
3 Partially correct 1 ms 208 KB Number of queries: 9
4 Partially correct 2 ms 208 KB Number of queries: 15

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 336 KB Number of queries: 8
2 Partially correct 7 ms 336 KB Number of queries: 10
3 Partially correct 19 ms 336 KB Number of queries: 28
4 Runtime error 3 ms 592 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 416 KB Number of queries: 9
2 Partially correct 12 ms 336 KB Number of queries: 12
3 Partially correct 22 ms 336 KB Number of queries: 28
4 Runtime error 2 ms 592 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -