oj.uz

Submission #1075709

# Submission time Handle Problem Language Result Execution time Memory
1075709 2024-08-26T08:45:39 Z Abito Simurgh (IOI17_simurgh) C++17
13 / 100
 3000 ms 436 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int par[30],sz[30];
int getpar(int x){
	if (x==par[x]) return x;
	return par[x]=getpar(par[x]);
}
void link(int x,int y){
	x=getpar(x);
	y=getpar(y);
	if (x==y) return;
	if (sz[x]>sz[y]) swap(x,y);
	sz[y]+=sz[x];
	par[x]=y;
	return;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	int m=u.size();
	for (int mask=0;mask<(1<<m);mask++){
		if (__builtin_popcount(mask)!=n-1) continue;
		for (int i=0;i<n;i++) par[i]=i,sz[i]=1;
		for (int i=0;i<m;i++){
			if (mask&(1<<i)) link(u[i],v[i]);
		}
		if (sz[getpar(0)]!=n) continue;
		vector<int> r;
		for (int i=0;i<m;i++){
			if (mask&(1<<i)) r.pb(i);
		}
		int x=count_common_roads(r);
		if (x==n-1) return r;
	}
}

Compilation message

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

Subtask #1
13.0 / 13.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB correct
2 Correct 11 ms 348 KB correct
3 Correct 12 ms 436 KB correct
4 Correct 1 ms 348 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 1 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 1 ms 348 KB correct
13 Correct 5 ms 348 KB correct
14 Execution timed out 3067 ms 348 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB correct
2 Correct 11 ms 348 KB correct
3 Correct 12 ms 436 KB correct
4 Correct 1 ms 348 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 1 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 1 ms 348 KB correct
13 Correct 5 ms 348 KB correct
14 Execution timed out 3067 ms 348 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB correct
2 Correct 11 ms 348 KB correct
3 Correct 12 ms 436 KB correct
4 Correct 1 ms 348 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 1 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 1 ms 348 KB correct
13 Correct 5 ms 348 KB correct
14 Execution timed out 3067 ms 348 KB Time limit exceeded
15 Halted 0 ms 0 KB -