Submission #137406

#	Time	Username	Problem	Language	Result	Execution time	Memory
137406		wilwxk	Simurgh (IOI17_simurgh)	C++14	30 / 100	475 ms	3832 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=502;
int aresta[MAXN*MAXN][2];
vector<int> g[MAXN];
int rep[MAXN], tam[MAXN];
set<int> config, atual;
int n, m, tenho;
bool debug=0;

int find(int cur) {
	if(rep[cur]==cur) return cur;
	return rep[cur]=find(rep[cur]);
}
void une(int a, int b) {
	a=find(a); b=find(b);
	if(a==b) return;
	if(tam[a]<tam[b]) swap(a, b);
	rep[a]=b;
}

int query(set<int> &s) {
	// if(debug){for(auto cur : config) printf("%d ", cur);}
	int auxx[MAXN]; for(int i=0; i<n; i++) auxx[i]=rep[i];
	for(int i=0; i<n; i++) rep[i]=i;
	for(auto cur : s) une(aresta[cur][0], aresta[cur][1]);
	bool ok=0;
	for(int i=0; i<n; i++) if(find(i)!=find(0)) ok=1;  //deu ruim
	for(int i=0; i<n; i++) rep[i]=auxx[i];
	if(ok) return MAXN;
	vector<int> aux; for(auto cur : s) aux.push_back(cur);
	return count_common_roads(aux);
}

void atualiza() {
	for(int i=0; i<n; i++) rep[i]=i;
	for(auto cur : config) {
		int a=aresta[cur][0]; int b=aresta[cur][1];
		atual.insert(cur);
		une(a, b);
		// if(debug) printf("tree:: %d %d // %d\n", a, b, cur);
	}
	for(int i=0; i<m; i++) {
		int a=aresta[i][0]; int b=aresta[i][1];
		if(find(a)==find(b)) continue;
		atual.insert(i);
		une(a, b);
		// if(debug) printf("tree:: %d %d // %d\n", a, b, i);
	}
	tenho=query(atual);
}

bool testa(int ind) {
	// for(auto cur : atual) printf("%d ", cur); cout << endl;
	// printf("testa tirar %d\n", ind);
	config.clear();
	for(int i=0; i<n; i++) rep[i]=i;
	for(auto cur : atual) {
		if(cur==ind) continue;
		int a=aresta[cur][0];
		int b=aresta[cur][1];
		une(a, b);
		// printf("   une %d %d\n", a, b);
		config.insert(cur);
	}
	for(int i=0; i<m; i++) {
		if(i==ind) continue;
		int a=aresta[i][0];
		int b=aresta[i][1];
		// printf("   tenta %d // %d %d // %d %d\n", i, a, b, find(a), find(b));
		if(find(a)==find(b)) continue;
		config.insert(i);	
		// printf("   testa colocar %d >> %d %d\n", i, tenho, query(config));
		if(tenho<query(config)) {
			atual.erase(ind);
			atual.insert(i);
			return 1;
		}
		config.erase(i);
	}
	return 0;
}

std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) {
	n=N; m=U.size();
	for(int i=0; i<m; i++) {
		int a=U[i]; int b=V[i];
		aresta[i][0]=a; aresta[i][1]=b;
		g[a].push_back(i);
		g[b].push_back(i);
	}
	srand(time(0)+n+m);
	for(int i=0; i<n; i++) rep[i]=i, tam[i]=i;
	random_shuffle(tam, tam+n);

	atualiza();

	while(tenho<n-1) {
		for(auto cur : atual) {
			if(testa(cur)) {
				atualiza();
				break;
			}
		}
	}

	vector<int> respf; for(auto cur : atual) respf.push_back(cur);
	// if(debug) for(auto cur : respf) printf("%d ", cur);
	return respf;
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30