oj.uz

Submission #137406

# Submission time Handle Problem Language Result Execution time Memory
137406 2019-07-27T16:29:24 Z wilwxk Simurgh (IOI17_simurgh) C++14
30 / 100
 475 ms 3832 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 380 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 3 ms 376 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 376 KB correct
10 Correct 2 ms 376 KB correct
11 Correct 2 ms 376 KB correct
12 Correct 2 ms 376 KB correct
13 Correct 2 ms 376 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 380 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 3 ms 376 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 376 KB correct
10 Correct 2 ms 376 KB correct
11 Correct 2 ms 376 KB correct
12 Correct 2 ms 376 KB correct
13 Correct 2 ms 376 KB correct
14 Correct 24 ms 380 KB correct
15 Correct 21 ms 380 KB correct
16 Correct 49 ms 376 KB correct
17 Correct 58 ms 380 KB correct
18 Correct 41 ms 504 KB correct
19 Correct 61 ms 380 KB correct
20 Correct 47 ms 376 KB correct
21 Correct 36 ms 376 KB correct
22 Correct 2 ms 376 KB correct
23 Correct 3 ms 376 KB correct
24 Correct 2 ms 376 KB correct
25 Correct 2 ms 376 KB correct
26 Correct 2 ms 376 KB correct
27 Correct 2 ms 376 KB correct
28 Correct 2 ms 376 KB correct
29 Correct 2 ms 376 KB correct
30 Correct 2 ms 376 KB correct
31 Correct 2 ms 376 KB correct
32 Correct 2 ms 380 KB correct
33 Correct 2 ms 376 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 380 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 3 ms 376 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 376 KB correct
10 Correct 2 ms 376 KB correct
11 Correct 2 ms 376 KB correct
12 Correct 2 ms 376 KB correct
13 Correct 2 ms 376 KB correct
14 Correct 24 ms 380 KB correct
15 Correct 21 ms 380 KB correct
16 Correct 49 ms 376 KB correct
17 Correct 58 ms 380 KB correct
18 Correct 41 ms 504 KB correct
19 Correct 61 ms 380 KB correct
20 Correct 47 ms 376 KB correct
21 Correct 36 ms 376 KB correct
22 Correct 2 ms 376 KB correct
23 Correct 3 ms 376 KB correct
24 Correct 2 ms 376 KB correct
25 Correct 2 ms 376 KB correct
26 Correct 2 ms 376 KB correct
27 Correct 2 ms 376 KB correct
28 Correct 2 ms 376 KB correct
29 Correct 2 ms 376 KB correct
30 Correct 2 ms 376 KB correct
31 Correct 2 ms 376 KB correct
32 Correct 2 ms 380 KB correct
33 Correct 2 ms 376 KB correct
34 Incorrect 475 ms 1532 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Incorrect 371 ms 3832 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 380 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 3 ms 376 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 376 KB correct
10 Correct 2 ms 376 KB correct
11 Correct 2 ms 376 KB correct
12 Correct 2 ms 376 KB correct
13 Correct 2 ms 376 KB correct
14 Correct 24 ms 380 KB correct
15 Correct 21 ms 380 KB correct
16 Correct 49 ms 376 KB correct
17 Correct 58 ms 380 KB correct
18 Correct 41 ms 504 KB correct
19 Correct 61 ms 380 KB correct
20 Correct 47 ms 376 KB correct
21 Correct 36 ms 376 KB correct
22 Correct 2 ms 376 KB correct
23 Correct 3 ms 376 KB correct
24 Correct 2 ms 376 KB correct
25 Correct 2 ms 376 KB correct
26 Correct 2 ms 376 KB correct
27 Correct 2 ms 376 KB correct
28 Correct 2 ms 376 KB correct
29 Correct 2 ms 376 KB correct
30 Correct 2 ms 376 KB correct
31 Correct 2 ms 376 KB correct
32 Correct 2 ms 380 KB correct
33 Correct 2 ms 376 KB correct
34 Incorrect 475 ms 1532 KB WA in grader: NO
35 Halted 0 ms 0 KB -