제출 #137751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137751		MAMBA	Simurgh (IOI17_simurgh)	C++17	30 / 100	434 ms	3320 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);
			break;
		}
	if (res == -1) return v;
	return res;
}

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]));
			adj[dd.getPar(v[i])].pb(dd.getPar(u[i]));
		}

		int me = dfs(dd.getPar(0));

		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();
			}
		}
		while (B.empty());
		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;
}

컴파일 시 표준 에러 (stderr) 메시지

simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (local.size() < n - 1) {
         ~~~~~~~~~~~~~^~~~~~~

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