Submission #1319181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319181		sonarcht	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	9 ms	508 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int i, j, l, r, mid, p, q, k, t, n, m, a, b, c, d, ans, cnt, res, cor[200005], tin[200005];
const long long mod = 999993143, mod2 = 999993469;
string s;
bool check;
vector <int> adj[200005], qq;
void dfs (int u, int v){
	t += 1;
	int i, p;
	tin[u] = t;
	for (i = 0; i < adj[u].size(); i += 1){
		p = adj[u][i];
		if (p != v){
			dfs(p, u);
		}
	}
}

int findEgg (int N, vector <pair <int, int> > bridges){
	n = N;
	for (i = 1; i <= n; i += 1){
		adj[i].clear();
	}
	for (i = 0; i < bridges.size(); i += 1){
		a = bridges[i].first;
		b = bridges[i].second;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	t = 0;
	dfs(1, -1);
	for (i = 1; i <= n; i += 1){
		cor[tin[i]] = i;
	}
	l = 1;
	r = n - 1;
	ans = cor[n];
	while (l <= r){
		mid = (l + r) / 2;
		qq.clear();
		for (i = 1; i <= mid; i += 1){
			qq.push_back(cor[i]);
		}
		res = query(qq);
		if (res == 1){
			ans = cor[mid];
			r = mid - 1;
		}
		else{
			l = mid + 1;
		}
	}
	return ans;
}//

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