oj.uz

Submission #270512

# Submission time Handle Problem Language Result Execution time Memory
270512 2020-08-17T17:01:49 Z rqi Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 24 ms 512 KB 
#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

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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Number of queries: 4
2 Correct 1 ms 384 KB Number of queries: 4
3 Correct 1 ms 384 KB Number of queries: 4
4 Correct 1 ms 384 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Number of queries: 8
2 Correct 15 ms 384 KB Number of queries: 9
3 Correct 20 ms 512 KB Number of queries: 9
4 Correct 17 ms 512 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 512 KB Number of queries: 9
2 Correct 20 ms 384 KB Number of queries: 9
3 Correct 24 ms 384 KB Number of queries: 9
4 Correct 18 ms 512 KB Number of queries: 9