Submission #270512

#	Time	Username	Problem	Language	Result	Execution time	Memory
270512		rqi	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	24 ms	512 KiB

eastereggs

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

using namespace std;

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()

const int mx = 550;
int N;
vi adj[mx];
int ans;

int cnt;
vi q;
vi roots;
bool visited[mx];
bool inComp[mx];

void dfs(int node){
	visited[node] = 1;
	if(cnt == 0){
		roots.pb(node);
		return;
	}

	cnt--;
	q.pb(node);

	for(auto u: adj[node]){
		if(visited[u]) continue;
		dfs(u);
	}
}

vi origadj[mx];
int par[mx][15];
int depth[mx];

void genPar0(int node, int prv = 0){
	if(node == 1){
		depth[node] = 0;
	}
	par[node][0] = prv;
	for(auto u: origadj[node]){
		if(u == prv) continue;
		depth[u] = depth[node]+1;
		genPar0(u, node);
	}
}

int getPar(int node, int jmp){
	for(int i = 14; i >= 0; i--){
		if((1<<i) <= jmp){
			node = par[node][i];
			jmp-=(1<<i);
		}
	}
	return node;
}

int lca(int a, int b){
	if(depth[a] < depth[b]) swap(a, b);
	if(depth[a] > depth[b]){
		a = getPar(a, depth[a]-depth[b]);
	}
	if(a == b) return a;
	for(int i = 14; i >= 0; i--){
		if(par[a][i] != par[b][i]){
			a = par[a][i];
			b = par[b][i];
		}
	}
	return par[a][0];
}

int num[mx];

void genNum(int node, int prv = 0){
	for(auto u: origadj[node]){
		if(u == prv) continue;
		genNum(u, node);
		num[node]+=num[u];
	}
}

vi makeConnected(vi nodes, vpi eds){
	assert(sz(nodes) >= 1);
	int R = nodes[0];
	for(auto u: eds){
		inComp[u.f] = inComp[u.s] = 0;
	}
	for(auto u: nodes){
		inComp[u] = 1;
	}
	for(int i = 0; i <= N; i++){
		num[i] = 0;
	}
	for(auto u: eds){
		if(inComp[u.f] && inComp[u.s]){
			num[u.f]++;
			num[u.s]++;
			num[lca(u.f, u.s)]--;
			num[par[lca(u.f, u.s)][0]]--;
		}
	}
	genNum(1);
	for(auto u: nodes){
		num[u]++;
	}
	vi res;
	for(int i = 1; i <= N; i++){
		if(num[i] > 0) res.pb(i);
	}
	return res;
}

void search(vi nodes, vpi eds){
	// cout << "nodes: ";
	// for(auto u: nodes){
	// 	cout << u << " ";
	// }
	// cout << "\n";
	// cout << "eds: ";
	// for(auto u: eds){
	// 	cout << "(" << u.f << "," << u.s << "), ";
	// }
	// cout << "\n";
	assert(sz(nodes) >= 1);
	int R = nodes[0];
	if(sz(nodes) == 1){
		ans = R;
		return;
	}
	
	for(auto u: nodes){
		adj[u].clear();
		visited[u] = 0;
	}
	for(auto u: eds){
		adj[u.f].pb(u.s);
		adj[u.s].pb(u.f);
	}

	cnt = sz(nodes)/2;
	q.clear();
	roots.clear();
	dfs(R); //generate q

	// cout << "q: ";
	// for(auto u: q){
	// 	cout << u << " ";
	// }
	// cout << "\n";

	vi Q = makeConnected(q, eds); //turn all edges between members of q into paths (offline), return all nodes
	
	// cout << "Q: ";
	// for(auto u: Q){
	// 	cout << u << " ";
	// }
	// cout << "\n";

	for(auto u: nodes){
		inComp[u] = 0;
	}
	for(auto u: q){
		inComp[u] = 1;
	}
	if(query(Q) == 1){
		vi NODES;
		vpi EDS;

		for(auto u: nodes){
			if(inComp[u]) NODES.pb(u);
		}
		for(auto u: eds){
			if(inComp[u.f] && inComp[u.s]) EDS.pb(u);
		}
		search(NODES, EDS);
	}
	else{
		vi NODES;
		vpi EDS;

		for(auto u: nodes){
			if(!inComp[u]) NODES.pb(u);
		}
		for(auto u: eds){
			if(!inComp[u.f] && !inComp[u.s]) EDS.pb(u);
		}
		assert(sz(roots) >= 1);
		for(int i = 1; i < sz(roots); i++){
			EDS.pb(mp(roots[0], roots[i]));
		}
		search(NODES, EDS);
	}

}

int findEgg(int _N, vector<pi> bridges)
{
	N = _N;
	for(int i = 0; i <= N; i++){
		origadj[i].clear();
		for(int j = 0; j < 15; j++){
			par[i][j] = 0;
		}
	}
	for(auto u: bridges){
		origadj[u.f].pb(u.s);
		origadj[u.s].pb(u.f);
	}
	genPar0(1);
	for(int j = 1; j < 15; j++){
		for(int i = 1; i <= N; i++){
			par[i][j] = par[par[i][j-1]][j-1];
		}
	}

	vi nodes;
	for(int i = 1; i <= N; i++){
		nodes.pb(i);
	}

	search(nodes, bridges);
	return ans;
}

Compilation message (stderr)

eastereggs.cpp: In function 'vi makeConnected(vi, vpi)':
eastereggs.cpp:96:6: warning: unused variable 'R' [-Wunused-variable]
   96 |  int R = nodes[0];
      |      ^

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