Submission #300785

#	Time	Username	Problem	Language	Result	Execution time	Memory
300785		JPN20	Simurgh (IOI17_simurgh)	C++17	51 / 100	266 ms	9472 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];

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> find_roads(int n, vector<int> u, vector<int> v) {
	// Step #1. 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];
	
	// Step #2. 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 #3. Get Color
	for (int i = 0; i < M; i++) Answer[i] = -1;
	for (int i : R) {
		solve(i);
	}
	
	// Step #4. Get Answer
	vector<int> FinalAns;
	for (int i = 0; i < M; i++) {
		if (Answer[i] == 1) FinalAns.push_back(i);
	}
	return FinalAns;
}

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