oj.uz

Submission #73485

# Submission time Handle Problem Language Result Execution time Memory
73485 2018-08-28T10:20:23 Z SmsS Simurgh (IOI17_simurgh) C++14
0 / 100
 39 ms 2640 KB 
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
#define for2(a,b,c) for(int a = b; a < c; a++)
#include "simurgh.h"

const int maxn = 510;
int adj[maxn][maxn];
bool seen[maxn];
bool burn[maxn];

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	std::vector<int> res(n - 1);
	int m = u.size();

	srand(10);
	vector<int> sh(n);
	for2(i,0,n) sh[i] = i;
	random_shuffle(sh.begin(),sh.end());
	for2(i,0,m){

	/////////////


		continue;

	///////////////
		u[i] = sh[u[i]];
		v[i] = sh[v[i]];
	}

	for2(i,0,m) adj[u[i]][v[i]] = adj[v[i]][u[i]] = i;
	
	vector<int> tree;
	tree.pb(0);
	seen[0] = 1;
	int rep = 0;
	while(tree.size() != n){
//		cout << rep << endl;
//		for(auto x : res) cout <<x << ' ';
//		cout << endl;

		for(auto x : tree)if(!burn[x]){
			burn[x] = 1;
			int cnt = rep;
			for2(i,0,n)if(!seen[i]) res[cnt++] = adj[i][x];
			int get = (count_common_roads(res));
			if(rep == get) continue;
//			cout << x << endl;
			int last = -1;
			cnt = rep;
			for2(i,0,n) if(!seen[i]){
				if(last != -1){
					res[cnt++] = adj[i][last];
				}
				last = i;
			}
//			for(auto x : res) cout << x << ' ';
//			cout << endl;

			vector<int> c;
			int mx = 0;
			for2(i,0,n)if(!seen[i]){
				res[cnt] = adj[i][x];
				c.pb(count_common_roads(res));
//				cout << c.back() << endl;
				mx = max(mx,c.back());
			}
//			cout << mx << endl;
			cnt = 0;
			for2(i,0,n) if(!seen[i]){
				if(c[cnt++] == mx){
					tree.pb(i);
					seen[i] = 1;
					res[rep] = adj[i][x];
					rep++;
				}
			}
		}
	}
	return res;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(tree.size() != n){
        ~~~~~~~~~~~~^~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 520 KB correct
2 Correct 3 ms 536 KB correct
3 Incorrect 39 ms 2640 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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