oj.uz

Submission #283813

# Submission time Handle Problem Language Result Execution time Memory
283813 2020-08-26T07:34:09 Z emanIaicepsa Simurgh (IOI17_simurgh) C++14
30 / 100
 30 ms 5220 KB 
#include "simurgh.h"
#include<bits/stdc++.h>
#define pb emplace_back
#define vi vector<int>
#define pii pair<int,int>
#define fi first
#define se second
#define all(n) (n).begin(),(n).end()
using namespace std;
 
vi ans, pos, pos2, U, V;
 
int pa[505], N, M, dead[25005];
void init(){
	for(int i=0;i<N;i++) pa[i] = i;
}
int fp(int x){
	if(pa[x] == x) return x;
	return pa[x] = fp(pa[x]);
}
void uni(int x,int y){
	x = fp(x), y = fp(y);
	assert(x != y);
	pa[x] = y;
}
 
void search_next(){
	init();
	random_shuffle(all(pos));
	int cnt = N;
	vi cur;
	for(auto &i:ans){
		uni(U[i], V[i]);
		cur.pb(i);
		cnt--;
	}
	vector<pii> tried;
	for(auto &i:pos){
		if(dead[i]) continue;
		if(cnt == 2){
			if(fp(U[i]) != fp(V[i])){
				cur.pb(i);
				assert(cur.size() == N-1);
				int common = count_common_roads(cur); 
				/* cout<<common<<" "<<i<<'\n'; */
				tried.pb(common,i);
				cur.pop_back();
			}
			else pos2.pb(i);
		}
		else{
			if(fp(U[i]) != fp(V[i])){
				cur.pb(i);
				uni(U[i], V[i]);
				cnt--;
			}
			pos2.pb(i);
		}
	}
	pair<int,int> mx = *max_element(all(tried));
	/* if(mx.fi == (int)ans.size() - 1){ */
	/* 	for(auto i:cur) dead[i] = 1; */
	/* } */
	for(auto &x : tried){
		if(x.fi == mx.fi){
			ans.pb(x.se);
		}
	}
	swap(pos, pos2);
	pos2.clear();
	/* for(auto i:pos) cout<<i<<" "; cout<<'\n'; */
}
// count_common_roads(vi v);
 
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	srand(time(0));
	M = u.size(), N = n;
	U = u, V = v;
	for(int i=0;i<M;i++) pos.pb(i);
	while(ans.size() < N - 1) search_next();
	/* for(auto i:ans) cout<<i<<" "; cout<<'\n'; */
	return ans;
}

Compilation message

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp: In function 'void search_next()':
simurgh.cpp:43:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |     assert(cur.size() == N-1);
      |            ~~~~~~~~~~~^~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:80:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |  while(ans.size() < N - 1) search_next();
      |        ~~~~~~~~~~~^~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB correct
2 Correct 0 ms 256 KB correct
3 Correct 0 ms 256 KB correct
4 Correct 0 ms 256 KB correct
5 Correct 0 ms 256 KB correct
6 Correct 0 ms 256 KB correct
7 Correct 0 ms 256 KB correct
8 Correct 0 ms 256 KB correct
9 Correct 0 ms 256 KB correct
10 Correct 0 ms 256 KB correct
11 Correct 0 ms 384 KB correct
12 Correct 0 ms 256 KB correct
13 Correct 0 ms 256 KB correct
14 Correct 3 ms 416 KB correct
15 Correct 3 ms 384 KB correct
16 Correct 3 ms 384 KB correct
17 Correct 3 ms 384 KB correct
18 Correct 1 ms 416 KB correct
19 Correct 3 ms 384 KB correct
20 Correct 3 ms 384 KB correct
21 Correct 2 ms 384 KB correct
22 Correct 2 ms 384 KB correct
23 Correct 2 ms 384 KB correct
24 Correct 2 ms 384 KB correct
25 Correct 1 ms 256 KB correct
26 Correct 2 ms 384 KB correct
27 Correct 2 ms 384 KB correct
28 Correct 1 ms 384 KB correct
29 Correct 1 ms 384 KB correct
30 Correct 2 ms 384 KB correct
31 Correct 2 ms 384 KB correct
32 Correct 2 ms 384 KB correct
33 Correct 2 ms 384 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB correct
2 Correct 0 ms 256 KB correct
3 Correct 0 ms 256 KB correct
4 Correct 0 ms 256 KB correct
5 Correct 0 ms 256 KB correct
6 Correct 0 ms 256 KB correct
7 Correct 0 ms 256 KB correct
8 Correct 0 ms 256 KB correct
9 Correct 0 ms 256 KB correct
10 Correct 0 ms 256 KB correct
11 Correct 0 ms 384 KB correct
12 Correct 0 ms 256 KB correct
13 Correct 0 ms 256 KB correct
14 Correct 3 ms 416 KB correct
15 Correct 3 ms 384 KB correct
16 Correct 3 ms 384 KB correct
17 Correct 3 ms 384 KB correct
18 Correct 1 ms 416 KB correct
19 Correct 3 ms 384 KB correct
20 Correct 3 ms 384 KB correct
21 Correct 2 ms 384 KB correct
22 Correct 2 ms 384 KB correct
23 Correct 2 ms 384 KB correct
24 Correct 2 ms 384 KB correct
25 Correct 1 ms 256 KB correct
26 Correct 2 ms 384 KB correct
27 Correct 2 ms 384 KB correct
28 Correct 1 ms 384 KB correct
29 Correct 1 ms 384 KB correct
30 Correct 2 ms 384 KB correct
31 Correct 2 ms 384 KB correct
32 Correct 2 ms 384 KB correct
33 Correct 2 ms 384 KB correct
34 Runtime error 24 ms 2688 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB correct
2 Correct 0 ms 256 KB correct
3 Runtime error 30 ms 5220 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB correct
2 Correct 0 ms 256 KB correct
3 Correct 0 ms 256 KB correct
4 Correct 0 ms 256 KB correct
5 Correct 0 ms 256 KB correct
6 Correct 0 ms 256 KB correct
7 Correct 0 ms 256 KB correct
8 Correct 0 ms 256 KB correct
9 Correct 0 ms 256 KB correct
10 Correct 0 ms 256 KB correct
11 Correct 0 ms 384 KB correct
12 Correct 0 ms 256 KB correct
13 Correct 0 ms 256 KB correct
14 Correct 3 ms 416 KB correct
15 Correct 3 ms 384 KB correct
16 Correct 3 ms 384 KB correct
17 Correct 3 ms 384 KB correct
18 Correct 1 ms 416 KB correct
19 Correct 3 ms 384 KB correct
20 Correct 3 ms 384 KB correct
21 Correct 2 ms 384 KB correct
22 Correct 2 ms 384 KB correct
23 Correct 2 ms 384 KB correct
24 Correct 2 ms 384 KB correct
25 Correct 1 ms 256 KB correct
26 Correct 2 ms 384 KB correct
27 Correct 2 ms 384 KB correct
28 Correct 1 ms 384 KB correct
29 Correct 1 ms 384 KB correct
30 Correct 2 ms 384 KB correct
31 Correct 2 ms 384 KB correct
32 Correct 2 ms 384 KB correct
33 Correct 2 ms 384 KB correct
34 Runtime error 24 ms 2688 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -