제출 #113558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
113558		E869120	Simurgh (IOI17_simurgh)	C++14	70 / 100	152 ms	6448 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

class UnionFind {
public:
	vector<int>par;
	void init(int sz) { par.resize(sz, -1); }
	int root(int pos) {
		if (par[pos] == -1) return pos;
		par[pos] = root(par[pos]);
		return par[pos];
	}
	void unite(int u, int v) { u = root(u); v = root(v); par[u] = v; }
};

int N, M, A[1 << 18], B[1 << 18], id[509][509], col[509], ming[509], represent[509], cnts; bool forced[509];
vector<int>G[509], ans; int rr[509][509];
vector<pair<int, int>> R[509];

void dfs(int root, int pos) {
	if (col[pos] >= 1) return;
	col[pos] = cnts;
	if (id[root][pos] >= 0) {
		represent[cnts] = pos;
		if (root > pos && rr[root][pos] == 1) ming[cnts] = pos;
	}
	for (int t : G[pos]) dfs(root, t);
}

void solve(int pos) {
	UnionFind UF; UF.init(N); vector<int>v;
	for (int i = 0; i < N; i++) { G[i].clear(); R[i].clear(); col[i] = 0; ming[i] = -1; represent[i] = 0; cnts = 0; forced[i] = false; }
	for (int i = 0; i < M; i++) {
		if (A[i] == pos || B[i] == pos) continue;
		if (UF.root(A[i]) == UF.root(B[i])) continue;
		UF.unite(A[i], B[i]); v.push_back(i);
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}
	for (int i = 0; i < N; i++) {
		if (i == pos || col[i] >= 1) continue;
		cnts++; dfs(pos, i);
	}
	for (int i = 1; i <= cnts; i++) { if (ming[i] >= 0) forced[ming[i]] = true; }
	for (int i = 0; i < N; i++) {
		if (id[pos][i] == -1) continue;
		if (pos > i && forced[i] == false) continue;
		
		vector<int>vec = v;
		for (int j = 1; j <= cnts; j++) { if (j == col[i]) continue; vec.push_back(id[pos][represent[j]]); }
		vec.push_back(id[pos][i]);
		int E = count_common_roads(vec);
		R[col[i]].push_back(make_pair(E, i));
	}
	for (int i = 1; i <= cnts; i++) {
		sort(R[i].begin(), R[i].end());
		reverse(R[i].begin(), R[i].end());
		for (int j = 0; j < R[i].size(); j++) { if (R[i][j].first == R[i][0].first) { ans.push_back(id[pos][R[i][j].second]); rr[pos][R[i][j].second] = 1; rr[R[i][j].second][pos] = 1; } }
	}
}

void find_array(int pos) {
	int cx = pos + 1, cnt = 0;
	for (int i = 0; i < pos; i++) { cnt += max(rr[pos][i], rr[i][pos]); }
	while (true) {
		int cl = cx, cr = N, cm, minx = (1 << 30);
		for (int i = 0; i < 10; i++) {
			cm = (cl + cr) / 2;
			
			vector<int> vec; for (int j = 0; j < N; j++) { if (j == pos) continue; if (j <= cm) vec.push_back(id[pos][j]); else vec.push_back(id[0][j]); }
			int E = count_common_roads(vec);
			for (int j = cm + 1; j < N; j++) { if (j == pos) continue; E -= rr[0][j]; }
			//cout << "pos = " << pos << ", cm = " << cm << ", E = " << E << ", cnt = " << cnt << endl;
			if (E >= cnt + 1) { minx = min(minx, cm); cr = cm; }
			else { cl = cm; }
		}
		if (minx == (1 << 30)) break;
		ans.push_back(id[pos][minx]); rr[pos][minx] = 1; rr[minx][pos] = 1; //cout << "# " << pos << " " << minx << endl;
		cx = minx + 1; cnt++;
	}
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	N = n; M = u.size();
	for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) id[i][j] = -1; }
	for (int i = 0; i < M; i++) { id[u[i]][v[i]] = i; id[v[i]][u[i]] = i; A[i] = u[i]; B[i] = v[i]; }
	if (N * (N - 1) / 2 != M) {
		for (int i = 0; i < N; i++) solve(i);
	}
	else {
		solve(0);
		for (int j = 1; j < N; j++) find_array(j);
	}
	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());
	//cout << "#answer = "; for (int i = 0; i < ans.size(); i++) cout << ans[i] << ", "; cout << endl;
	return ans;
}

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

simurgh.cpp: In function 'void solve(int)':
simurgh.cpp:59:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < R[i].size(); j++) { if (R[i][j].first == R[i][0].first) { ans.push_back(id[pos][R[i][j].second]); rr[pos][R[i][j].second] = 1; rr[R[i][j].second][pos] = 1; } }
                   ~~^~~~~~~~~~~~~

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