Submission #73485

#	Time	Username	Problem	Language	Result	Execution time	Memory
73485		SmsS	Simurgh (IOI17_simurgh)	C++14	0 / 100	39 ms	2640 KiB

simurgh

#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 (stderr)

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
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30