제출 #1161535

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161535		turska	Easter Eggs (info1cup17_eastereggs)	C++20	71.60 / 100	9 ms	544 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;


vector<vector<int>> at_depth, adj;
vector<int> from, dist;

void dfs(int v, int p, bool save) {
	if (save) at_depth[dist[v]].push_back(v);
	for (auto u: adj[v]) if (u!=p) {
		dist[u] = dist[v]+1;
		from[u] = v;
		dfs(u, v, save);
	}
}



int findEgg(int N, vector <pair<int, int>> bridges) {
	from.assign(N, 0);
	dist = from;
	adj.assign(N, {});
	at_depth = adj;

	for (int i=0; i<N-1; i++) {
		auto [u, v] = bridges[i];
		u--; v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	/*

	dfs(0, -1, 0);
	int s = 0;
	for (int i=0; i<N; i++) if (dist[i]>dist[s]) s = i;
	dist[s] = 0;
	dfs(s, -1, 0);
	int e = s;
	for (int i=0; i<N; i++) if (dist[i]>dist[e]) e = i;
	for (int i=0; i<dist[e]/2; i++) {
		e = from[e];
	} */
	int e = 0;

	dist[e] = 0;
	dfs(e, -1, 1);

	int r = *max_element(dist.begin(), dist.end());
	int l = -1;

	while (r-l>1) {
		int m = (r+l)/2;
		vector<int> st;
		for (int i=0; i<=m; i++) for (auto v: at_depth[i]) st.push_back(v+1);
		if (query(st)) r = m;
		else l = m;
	}
	vector<int> base;
	for (int i=0; i<r; i++) for (auto v: at_depth[i]) base.push_back(v+1);
	vector<int> a;
	for (auto v: at_depth[r]) a.push_back(v+1);
	while (a.size()>1) {
		vector<int> b;
		while (a.size()>b.size()) {
			b.push_back(a.back());
			a.pop_back();
		}
		vector<int> c = base;
		for (auto v: b) c.push_back(v);
		if (query(c)) a = b;
	}
	return a[0];
} 

• Subtask 1: 32 / 40
• Subtask 2: 26.4 / 40
• Subtask 3: 13.2 / 20