Submission #359911

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
359911	2021-01-27T09:58:13 Z	amunduzbaev	Easter Eggs (info1cup17_eastereggs)	C++14	0 / 100	84 ms	1132 KB

eastereggs

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

#ifndef EVAL
#include "grader.cpp"
#endif

#define pb push_back
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define pii pair<int, int>

using namespace std;

const int NN = 513;
vector<pii> edges[NN];
vector<int> vv[NN];
int nn, used[NN];

void dfs(int u, int p = -1){
	//cout<<u<<" ";
	vv[u].pb(u);
	for(auto x:edges[u]){
		if(x.ff == p || used[x.ss]) continue;
		dfs(x.ff, u);
		for(auto xx:vv[x.ff]) vv[u].pb(xx);
	}
}

int dfs_cc(int u, int p = -1){
	pii mx = {-1, -1};
	for(auto x:edges[u]){
		if(used[x.ss] || x.ff == p) continue;
		if(sz(vv[x.ff]) > mx.ff) mx.ff = sz(vv[x.ff]), mx.ss = x.ff;
	}
	if(mx.ff * 2 >= nn) return dfs_cc(mx.ss, u);
	return u;
}

int solve(int cur){
	//for(int i=0;i<5;i++) cout<<used[i]<<" ";
	//cout<<"\n";
	
	for(int i=0;i<NN;i++) vv[i].clear();
	dfs(cur);
	
	//cout<<nn<<" "<<cur<<" ";
	if(nn == 1) return 0;
	int centr = dfs_cc(cur);
	
	//cout<<"\n";
	//cout<<cur<<" "<<centr<<"\n";
	
	for(int i=0;i<NN;i++) vv[i].clear();
	dfs(centr);
	//cout<<"\n";
	//cout<<centr<<"\n";
	vector<pair<int, pii>> childs;
	for(auto x:edges[centr]) childs.pb({sz(vv[x.ff]), x});
	
	sort(childs.begin(), childs.end());
	//cout<<centr<<"\n";
	//for(auto x:childs) cout<<x.ss.ff<<" "<<x.ff<<"\n";
	//cout<<"______\n";
	vector<int> qq = vv[childs.back().ss.ff];
	qq.pb(centr);
	
	vector<int> uu(NN, 0);
	uu[childs.back().ss.ss] = 1;
	childs.pop_back();
	
	int last = sz(qq);
	int nw = -1;
	int start;
	for(auto x:childs){
		nw = x.ff + last;
		if(abs(nw*2 - nn) < abs(nn - last*2)){
			for(auto xx : vv[x.ss.ff]) qq.pb(xx);
		}else { start = x.ss.ff; break; }
		uu[x.ss.ss] = 1;
	}
	for(auto &x:qq) x += 1;
	int res = query(qq);
	
	//for(auto x:qq) cout<<x<<" ";
	//cout<<"\n";
	
	if(nn == 2 && res){
		int bb = qq.back(); qq.pop_back();
		if(query({bb})) return bb-1;
		return qq.back()-1;
	}
	
	if(res){
		for(auto x:edges[centr]){
			//cout<<uu[x.ss]<<" "<<x.ss<<"\n";
			if(uu[x.ss]) continue;
			else used[x.ss] = 1;
		}
		
		nn = sz(qq);
		if(nn == 1) return centr;
		return solve(centr);
	}else{
		for(auto x:edges[centr]){
			if(uu[x.ss]) used[x.ss] = 1;
		}
		nn = (nn - sz(qq));
		if(nn == 1) return start;
		nn++;
		
		return solve(centr);
	}
	return 0;
}

int findEgg (int N, vector < pair < int, int > > bridges){
	memset(used, 0, sizeof used);
	for(int i=0;i<NN;i++) edges[i].clear(), vv[i].clear();
	nn = N;
	for(int i=0;i<sz(bridges);i++){
		edges[bridges[i].ff-1].pb({bridges[i].ss-1, i});
		edges[bridges[i].ss-1].pb({bridges[i].ff-1, i});
	}
	//nn = N;
	//dfs(0);
	return solve(0)+1;
}

Subtask #1

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	2 ms	364 KB	Number of queries: 6
2	Runtime error	1 ms	492 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #2

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	14 ms	492 KB	Number of queries: 10
2	Runtime error	5 ms	1004 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	84 ms	1132 KB	Number of queries: 11
2	Runtime error	3 ms	876 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-