Submission #1146510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146510		crispxx	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	186 ms	596 KiB

eastereggs

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

// #include "grader.cpp"

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define nl '\n'

int findEgg(int n, vector <pair<int, int>> edges) {
	
	vector<set<int>> adj(n);
	
	for(auto &[u, v] : edges) {
		u--, v--;
		adj[u].emplace(v);
		adj[v].emplace(u);
	}
	
	vector<int> isl;
    
    auto dfs = [&](auto &&dfs, int v, int p) -> void {
		isl.pb(v + 1);
		for(auto to : adj[v]) {
			if(to == p) continue;
			dfs(dfs, to, v);
		}
	};
	
	auto dfs1 = [&](auto &&dfs, int v, int p, vector<vector<int>> &chd) -> void {
		for(auto to : adj[v]) {
			if(to == p) continue;
			
			dfs(dfs, to, v, chd);
			
			for(auto i : chd[to]) chd[v].pb(i);
		}
	};
	
	set<int> vis;
	
	for(int i = 0; i < n; i++) vis.emplace(i);
	
	while(true) {
		
		bool flag = false;
		
		for(auto [u, v] : edges) {
			if(vis.find(u) == vis.end()) continue;
			if(vis.find(v) == vis.end()) continue;
			
			adj[u].erase(v);
			adj[v].erase(u);
			
			dfs(dfs, u, -1);
			
			auto isl1 = isl;
			
			isl.clear();
			
			dfs(dfs, v, -1);
			
			auto isl2 = isl;
			
			isl.clear();
			
			int x = isl1.size(), y = isl2.size();
			
			int cur = x + y;
			
			if((x == cur / 2 && y == (cur + 1) / 2) || (x == (cur + 1) / 2 && y == cur / 2)) {
				// cout << "u v " << u + 1 << ' ' << v + 1 << ": ";
				if(query(isl1)) {
					if(x == 1) {
						return isl1[0];
					}
					for(auto to : isl2) {
						to--;
						vis.erase(to);
						// cout << to + 1 << ' ';
					}
				} else {
					if(y == 1) {
						return isl2[0];
					}
					for(auto to : isl1) {
						to--;
						vis.erase(to);
						// cout << to + 1 << ' ';
					}
				}
				// cout << nl;
				flag = true;
				break;
			}
			
			adj[u].emplace(v);
			adj[v].emplace(u);
		}
		
		
		if(!flag) {
			for(int r = 0; r < n; r++) {
				
				if(vis.find(r) == vis.end()) continue;
				
				vector <vector<int>> chd(n);
				
				for(int i = 0; i < n; i++) chd[i].pb(i);
				
				dfs1(dfs1, r, -1, chd);
				
				vector<pair<int, int>> tr;
				
				for(auto to : adj[r]) {
					tr.emplace_back(chd[to].size(), to);
				}
				
				sort(all(tr));
				
				vector<int> isl1;
				
				isl1.pb(r + 1);
				
				for(int i = 0; i < (int)tr.size(); i++) {
					
					int v = tr[i].second;
					
					for(auto to : chd[v]) {
						isl1.pb(to + 1);
					}
					
					vector<int> isl2;
					
					isl2.pb(r + 1);
					
					for(int j = i + 1; j < (int)tr.size(); j++) {
						int v1 = tr[j].second;
						for(auto to : chd[v1]) isl2.pb(to + 1);
					}
					
					int x = isl1.size(), y = isl2.size();
					int cur = x + y;
					
					if((x == cur / 2 && y == (cur + 1) / 2) || (x == (cur + 1) / 2 && y == cur / 2)) {
						
						// cout << "r " << r + 1 << ": ";
						
						if(query(isl1)) {
							
							for(auto to : isl2) {
								to--;
								// cout << to + 1 << ' ';
								if(to == r) continue;
								vis.erase(to);
								adj[r].erase(to);
							}
							
						} else {
							
							for(auto to : isl1) {
								to--;
								// cout << to + 1 << ' ';
								if(to == r) continue;
								vis.erase(to);
								adj[r].erase(to);
							}
							
						}
						
						// cout << nl;
						
						flag = true;
						break;
					}
				}
				if(flag) break;
			}
		}
		
		
		if(!flag) break;
		
		
	}
	
	return -1;
}

/**

5
1 2
1 3
2 4
3 5
5
1 2 3 4 5


**/

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