Submission #137736

#	Time	Username	Problem	Language	Result	Execution time	Memory
137736		MAMBA	Simurgh (IOI17_simurgh)	C++17	0 / 100	2 ms	376 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define pb push_back

typedef vector<int> vi;

const int N = 510;

struct dsu {
	int par[N];
	dsu() {
		iota(par , par + N, 0);
	}
	int getPar(int v) {
		return v == par[v] ? v : par[v] = getPar(par[v]);
	}
	inline bool merge(int a, int b) {
		if ((a = getPar(a)) == (b = getPar(b))) return false;
		par[a] = b;
		return true;
	}
};

dsu dd;
bitset<N> mark;

vi adj[N];

int dfs(int v) {
	mark[v] =true;
	int res = -1;
	for (auto e : adj[v])
		if (!mark[e]) 
			res = dfs(e);
	if (res == -1) return v;
}

vi find_roads(int n, vi u, vi v) {
	int m = u.size();

	vi local;

	while (local.size() < n - 1) {

		mark.reset();
		rep(i , 0 , n) adj[i].clear();
		rep(i , 0 , m) adj[dd.getPar(u[i])].pb(dd.getPar(v[i]));

		int me = dfs(1);

		dsu ds;
		vi ask = local;
		for (auto e : ask) ds.merge(u[e] , v[e]);
		rep(i , 0 , m) 
			if (ds.getPar(u[i]) != me && ds.getPar(v[i]) != me && ds.merge(u[i] , v[i]))
				ask.pb(i);
		vi A, B;
			rep(i , 0 , m) {
				int a = ds.getPar(u[i]);
				int b = ds.getPar(v[i]);
				if ((a == me && b != me) || (b == me && a != me)) {
					A.pb(i);
					ask.pb(i);
					B.pb(count_common_roads(ask));
					ask.pop_back();
				}
			}
		int res = *max_element(B.begin(), B.end());
		rep(i , 0 , A.size())
			if (B[i] == res) {
				local.pb(A[i]);
				dd.merge(u[A[i]] , v[A[i]]);
			}
	}

	return local;
}

Compilation message (stderr)

simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (local.size() < n - 1) {
         ~~~~~~~~~~~~~^~~~~~~
simurgh.cpp: In function 'int dfs(int)':
simurgh.cpp:40:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30