제출 #832481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832481		MadokaMagicaFan	Simurgh (IOI17_simurgh)	C++14	51 / 100	78 ms	2444 KiB

simurgh

#include "bits/stdc++.h"
#include "simurgh.h"
using namespace std;
using ll = long long;
#define pb push_back
#define sz(v) ((int)v.size())

int p[500];
int getp(int x) { return p[x] = (x == p[x] ? x : getp(p[x])); }
int uni(int a, int b) {
	a = getp(a);
	b = getp(b);
	if (a == b) return 0;
	p[a] = b;
	return 1;
}

vector<int>
find_roads(int n, vector<int> u, vector<int> v) {
	int m = sz(u);
	vector<int> ans, r, us(m, 0), z;
	for (int i = 0; i < n-1; ++i) {
		for (int i = 0; i < n; ++i) p[i] = i;
		int c = 0;
		if (sz(ans) == n-1) break;
		r = ans;
		for (auto x : ans) {
			c += uni(u[x], v[x]);
		}

		int p = 0;
		while (c < n-2) {
			if (uni(u[p], v[p])) {
				++c;
				r.pb(p);
			}
			++p;
		}

		while (us[p] || getp(u[p]) == getp(v[p]))
			++p;
		r.pb(p);
		z.clear();
		z.pb(p);
		assert(sz(r) == n-1);
		int x = count_common_roads(r);

		for (int j = p+1; j < m; ++j) {
			if(us[j]) continue;
			if (getp(u[j]) == getp(v[j])) continue;
			r[n-2] = j;
			us[j] = 1;
			int l = count_common_roads(r);
			if (l == x) {
				z.pb(j);
			} else if (l < x) {
				break;
			} else if (l > x) {
				z.clear(); z.pb(j);
				break;
			}
		}

		for (auto j : z)
			ans.pb(j);
	}

	return ans;
}

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