oj.uz

Submission #814875

# Submission time Handle Problem Language Result Execution time Memory
814875 2023-08-08T10:52:31 Z Dan4Life Simurgh (IOI17_simurgh) C++17
13 / 100
 3000 ms 320 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define pb push_back
#define sz(a) (int)a.size()
const int mxN = (int)5e2+2;
const int mxM = mxN*mxN/2;
int n, m, p[mxN], sz[mxN];
bool vis[mxM];
void init(int n){ for(int i = 0; i < n; i++) p[i]=i,sz[i]=1;}
int findSet(int i){return i==p[i]?i:p[i]=findSet(p[i]);}
bool isSameSet(int i, int j){return findSet(i)==findSet(j);}
void unionSet(int i, int j){
	int x = findSet(i), y = findSet(j);
	if(x==y) return;
	if(sz[x]<sz[y]) swap(x,y);
	p[y] = x; sz[x]+=sz[y];
}

int query(vector<int> &v){
	return count_common_roads(v);
}

vi find_roads(int N, vi u, vi v) {
	vi ans; m = sz(u); n = N;
	for(int mask = 0; mask < (1<<m); mask++){
		bool ok = 1; ans.clear(); init(n);
		for(int i = 0; i < m; i++){
			if(mask>>i&1){
				if(isSameSet(u[i],v[i])) ok=0;
				unionSet(u[i],v[i]); ans.pb(i);
			}
		}
		for(int i = 0; i < n; i++) ok&=isSameSet(i,0);
		if(ok and query(ans)==n-1) return ans;
	}
}

Compilation message

simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 212 KB correct
2 Correct 277 ms 292 KB correct
3 Correct 370 ms 288 KB correct
4 Correct 2 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 7 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 300 KB correct
10 Correct 2 ms 212 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 3 ms 212 KB correct
13 Correct 89 ms 300 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 212 KB correct
2 Correct 277 ms 292 KB correct
3 Correct 370 ms 288 KB correct
4 Correct 2 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 7 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 300 KB correct
10 Correct 2 ms 212 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 3 ms 212 KB correct
13 Correct 89 ms 300 KB correct
14 Execution timed out 3059 ms 320 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 212 KB correct
2 Correct 277 ms 292 KB correct
3 Correct 370 ms 288 KB correct
4 Correct 2 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 7 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 300 KB correct
10 Correct 2 ms 212 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 3 ms 212 KB correct
13 Correct 89 ms 300 KB correct
14 Execution timed out 3059 ms 320 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 212 KB correct
2 Execution timed out 3067 ms 212 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 212 KB correct
2 Correct 277 ms 292 KB correct
3 Correct 370 ms 288 KB correct
4 Correct 2 ms 212 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 7 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 300 KB correct
10 Correct 2 ms 212 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 3 ms 212 KB correct
13 Correct 89 ms 300 KB correct
14 Execution timed out 3059 ms 320 KB Time limit exceeded
15 Halted 0 ms 0 KB -