Submission #300835

#	Time	Username	Problem	Language	Result	Execution time	Memory
300835		JPN20	Simurgh (IOI17_simurgh)	C++17	70 / 100	271 ms	12540 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); if (u == v) return;
		par[u] = v;
	}
	bool same(int u, int v) {
		if (root(u) == root(v)) return true;
		return false;
	}
};

// Input, Output
int N, M;
int A[1 << 18], B[1 << 18];
int Answer[1 << 18];

// Spanning Tree
vector<int> X[1 << 18];
vector<int> R;
int BASE = 0;
int col[1 << 18];
bool istree[1 << 18];

// Subtask4
int idxs[509][509];
int ret[509][509];

void dfs(int pos, int par, int x) {
	col[pos] = x;
	for (int i : X[pos]) {
		if (i == par) continue;
		dfs(i, pos, x);
	}
}

void solve(int pos) {
	dfs(A[pos], B[pos], 1);
	dfs(B[pos], A[pos], 2);
	
	vector<int> vec1;
	vector<int> vec2;
	int idx = -1;
	for (int i = 0; i < M; i++) {
		if (istree[i] == true) continue;
		if (col[A[i]] == col[B[i]]) continue;
		if (Answer[i] != -1) { idx = i; continue; }
		vec1.push_back(i);
		vector<int> r;
		for (int j : R) { if (j != pos) r.push_back(j); }
		r.push_back(i);
		vec2.push_back(count_common_roads(r));
	}
	if (idx != -1) {
		vector<int> r;
		for (int j : R) { if (j != pos) r.push_back(j); }
		r.push_back(idx);
		int val = count_common_roads(r);
		Answer[pos] = Answer[idx] + (BASE - val);
	}
	else {
		Answer[pos] = 1;
		for (int j = 0; j < (int)vec2.size(); j++) {
			if (BASE < vec2[j]) Answer[pos] = 0;
			if (BASE > vec2[j]) Answer[pos] = 1;
		}
	}
	
	for (int i = 0; i < (int)vec1.size(); i++) {
		Answer[vec1[i]] = Answer[pos] + (vec2[i] - BASE);
	}
}

vector<int> solve_Subtask3() {
	// Step #1. Get Spanning Tree
	UnionFind UF; UF.init(N + 2);
	for (int i = 0; i < M; i++) {
		if (UF.same(A[i], B[i]) == true) continue;
		UF.unite(A[i], B[i]);
		X[A[i]].push_back(B[i]);
		X[B[i]].push_back(A[i]);
		istree[i] = true;
	}
	for (int i = 0; i < M; i++) {
		if (istree[i] == true) R.push_back(i);
	}
	BASE = count_common_roads(R);
	
	// Step #2. Get Color
	for (int i = 0; i < M; i++) Answer[i] = -1;
	for (int i : R) {
		solve(i);
	}
	
	// Step #3. Get Answer
	vector<int> FinalAns;
	for (int i = 0; i < M; i++) {
		if (Answer[i] == 1) FinalAns.push_back(i);
	}
	return FinalAns;
}

vector<int> solve_Subtask4() {
	for (int i = 0; i < M; i++) {
		idxs[A[i]][B[i]] = i;
		idxs[B[i]][A[i]] = i;
	}
	for (int i = 0; i < N - 1; i++) R.push_back(idxs[i][i + 1]);
	BASE = count_common_roads(R);
	
	// GETBS
	if (BASE == 0) {
		for (int i = 0; i < N - 1; i++) ret[i][i + 1] = 0;
		for (int i = 0; i < N - 1; i++) ret[i + 1][i] = 0;
	}
	else if (BASE == N - 1) {
		for (int i = 0; i < N - 1; i++) ret[i][i + 1] = 1;
		for (int i = 0; i < N - 1; i++) ret[i + 1][i] = 1;
	}
	else {
		bool flag = false;
		for (int i = 0; i < N - 1; i++) {
			vector<int> r;
			for (int j = 0; j < N - 1; j++) {
				if (j == i) continue;
				r.push_back(idxs[j][j + 1]);
			}
			r.push_back(idxs[0][N - 1]);
			int val = count_common_roads(r);
			ret[i][i + 1] = BASE - val;
			ret[i + 1][i] = BASE - val;
			if (ret[i][i + 1] == -1) flag = true;
		}
		if (flag == true) {
			for (int i = 0; i < N - 1; i++) ret[i][i + 1] += 1;
			for (int i = 0; i < N - 1; i++) ret[i + 1][i] += 1;
		}
	}
	
	// PRFNL
	for (int i = 2; i < N; i++) {
		int cx = i - 1, cnt = 0;
		while (cx >= 1) {
			int cl = 0, cr = cx, cm, maxn = -1;
			for (int j = 0; j < 11; j++) {
				cm = (cl + cr) / 2;
				vector<int> r;
				for (int k = 0; k < cm; k++) r.push_back(idxs[k][k + 1]);
				for (int k = cm; k < i; k++) r.push_back(idxs[k][i]);
				for (int k = i; k < N - 1; k++) r.push_back(idxs[k][k + 1]);
				int ExpCost = BASE + cnt;
				for (int k = cm; k < i - 1; k++) { if (ret[k][k + 1] == 1) ExpCost -= 1; }
				int val = count_common_roads(r);
				if (val > ExpCost) { maxn = max(maxn, cm); cl = cm; }
				else { cr = cm; }
			}
			if (maxn == -1) break;
			//cout << maxn << " " << i << endl;
			cnt += 1;
			ret[i][maxn] = 1;
			ret[maxn][i] = 1;
			cx = maxn;
		}
	}
	
	// FINAL
	/*for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) cout << ret[i][j] << " ";
		cout << endl;
	}*/
	
	vector<int> FinalAns;
	for (int i = 0; i < M; i++) {
		if (ret[A[i]][B[i]] == 1) FinalAns.push_back(i);
	}
	return FinalAns;
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	// Input
	N = n;
	M = u.size();
	for (int i = 0; i < M; i++) A[i] = u[i];
	for (int i = 0; i < M; i++) B[i] = v[i];
	
	// Get Answer
	if (M == N * (N - 1) / 2) return solve_Subtask4();
	return solve_Subtask3();
}

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