oj.uz

Submission #428984

# Submission time Handle Problem Language Result Execution time Memory
428984 2021-06-15T16:10:04 Z vanic Simurgh (IOI17_simurgh) C++14
13 / 100
 3000 ms 332 KB 
#include "simurgh.h"
#include <iostream>
#include <cmath>
#include <stack>
#include <algorithm>

using namespace std;

const int maxn=505;

struct union_find{
	int parent[maxn];
	int sz[maxn];
	union_find(){
		for(int i=0; i<maxn; i++){
			parent[i]=i;
			sz[i]=1;
		}
	}
	int find(int x){
		if(parent[x]==x){
			return x;
		}
		return find(parent[x]);
	}
	int update(int x, int y){
		x=find(x);
		y=find(y);
		if(sz[x]>sz[y]){
			swap(x, y);
		}
		sz[y]+=sz[x];
		parent[x]=y;
		return x;
	}
	bool query(int x, int y){
		return find(x)==find(y);
	}
};

union_find U;

vector < int > a, b;
stack < int > s;
int n;
vector < int > q;

bool napravi(int x){
	if(x==(int)a.size()){
		int par=U.find(0);
		for(int i=0; i<n; i++){
			if(par!=U.find(i)){
				return 0;
			}
		}
		int br=count_common_roads(q);
		if(br==n-1){
			return 1;
		}
		return 0;
	}
	if(napravi(x+1)){
		return 1;
	}
	if(!U.query(a[x], b[x])){
		q.push_back(x);
		s.push(U.update(a[x], b[x]));
		if(napravi(x+1)){
			return 1;
		}
		U.sz[U.parent[s.top()]]-=U.sz[s.top()];
		U.parent[s.top()]=s.top();
		q.pop_back();
		s.pop();
	}
	return 0;
}

vector < int > find_roads(int nn, vector < int > u, vector < int > v) {
	a=u;
	b=v;
	n=nn;
	napravi(0);
	return q;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 5 ms 304 KB correct
3 Correct 3 ms 292 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 300 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 3 ms 204 KB correct
14 Execution timed out 3063 ms 332 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 5 ms 304 KB correct
3 Correct 3 ms 292 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 300 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 3 ms 204 KB correct
14 Execution timed out 3063 ms 332 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Incorrect 11 ms 204 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 5 ms 304 KB correct
3 Correct 3 ms 292 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 300 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 3 ms 204 KB correct
14 Execution timed out 3063 ms 332 KB Time limit exceeded
15 Halted 0 ms 0 KB -