oj.uz

Submission #300835

# Submission time Handle Problem Language Result Execution time Memory
300835 2020-09-17T14:10:19 Z JPN20 Simurgh (IOI17_simurgh) C++17
70 / 100
 271 ms 12540 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB correct
2 Correct 5 ms 6528 KB correct
3 Correct 5 ms 6528 KB correct
4 Correct 5 ms 6528 KB correct
5 Correct 5 ms 6528 KB correct
6 Correct 4 ms 6528 KB correct
7 Correct 5 ms 6528 KB correct
8 Correct 5 ms 6560 KB correct
9 Correct 5 ms 6528 KB correct
10 Correct 5 ms 6528 KB correct
11 Correct 5 ms 6528 KB correct
12 Correct 5 ms 6528 KB correct
13 Correct 5 ms 6528 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB correct
2 Correct 5 ms 6528 KB correct
3 Correct 5 ms 6528 KB correct
4 Correct 5 ms 6528 KB correct
5 Correct 5 ms 6528 KB correct
6 Correct 4 ms 6528 KB correct
7 Correct 5 ms 6528 KB correct
8 Correct 5 ms 6560 KB correct
9 Correct 5 ms 6528 KB correct
10 Correct 5 ms 6528 KB correct
11 Correct 5 ms 6528 KB correct
12 Correct 5 ms 6528 KB correct
13 Correct 5 ms 6528 KB correct
14 Correct 7 ms 6784 KB correct
15 Correct 8 ms 6784 KB correct
16 Correct 7 ms 6784 KB correct
17 Correct 7 ms 6528 KB correct
18 Correct 6 ms 6528 KB correct
19 Correct 7 ms 6528 KB correct
20 Correct 7 ms 6528 KB correct
21 Correct 6 ms 6528 KB correct
22 Correct 6 ms 6528 KB correct
23 Correct 6 ms 6528 KB correct
24 Correct 6 ms 6528 KB correct
25 Correct 5 ms 6528 KB correct
26 Correct 6 ms 6528 KB correct
27 Correct 6 ms 6528 KB correct
28 Correct 5 ms 6528 KB correct
29 Correct 5 ms 6528 KB correct
30 Correct 6 ms 6528 KB correct
31 Correct 6 ms 6528 KB correct
32 Correct 6 ms 6528 KB correct
33 Correct 6 ms 6528 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB correct
2 Correct 5 ms 6528 KB correct
3 Correct 5 ms 6528 KB correct
4 Correct 5 ms 6528 KB correct
5 Correct 5 ms 6528 KB correct
6 Correct 4 ms 6528 KB correct
7 Correct 5 ms 6528 KB correct
8 Correct 5 ms 6560 KB correct
9 Correct 5 ms 6528 KB correct
10 Correct 5 ms 6528 KB correct
11 Correct 5 ms 6528 KB correct
12 Correct 5 ms 6528 KB correct
13 Correct 5 ms 6528 KB correct
14 Correct 7 ms 6784 KB correct
15 Correct 8 ms 6784 KB correct
16 Correct 7 ms 6784 KB correct
17 Correct 7 ms 6528 KB correct
18 Correct 6 ms 6528 KB correct
19 Correct 7 ms 6528 KB correct
20 Correct 7 ms 6528 KB correct
21 Correct 6 ms 6528 KB correct
22 Correct 6 ms 6528 KB correct
23 Correct 6 ms 6528 KB correct
24 Correct 6 ms 6528 KB correct
25 Correct 5 ms 6528 KB correct
26 Correct 6 ms 6528 KB correct
27 Correct 6 ms 6528 KB correct
28 Correct 5 ms 6528 KB correct
29 Correct 5 ms 6528 KB correct
30 Correct 6 ms 6528 KB correct
31 Correct 6 ms 6528 KB correct
32 Correct 6 ms 6528 KB correct
33 Correct 6 ms 6528 KB correct
34 Correct 58 ms 8184 KB correct
35 Correct 262 ms 7640 KB correct
36 Correct 183 ms 7160 KB correct
37 Correct 17 ms 6528 KB correct
38 Correct 263 ms 7544 KB correct
39 Correct 239 ms 7288 KB correct
40 Correct 177 ms 7160 KB correct
41 Correct 62 ms 8088 KB correct
42 Correct 271 ms 7492 KB correct
43 Correct 134 ms 7040 KB correct
44 Correct 113 ms 7032 KB correct
45 Correct 131 ms 7012 KB correct
46 Correct 101 ms 6784 KB correct
47 Correct 45 ms 6656 KB correct
48 Correct 8 ms 6528 KB correct
49 Correct 16 ms 6528 KB correct
50 Correct 46 ms 6656 KB correct
51 Correct 134 ms 7032 KB correct
52 Correct 113 ms 7032 KB correct
53 Correct 106 ms 6904 KB correct
54 Correct 146 ms 7160 KB correct
55 Correct 120 ms 7160 KB correct
56 Correct 117 ms 7080 KB correct
57 Correct 115 ms 7032 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6528 KB correct
2 Correct 5 ms 6528 KB correct
3 Correct 160 ms 9984 KB correct
4 Correct 243 ms 12408 KB correct
5 Correct 250 ms 12488 KB correct
6 Correct 248 ms 12452 KB correct
7 Correct 251 ms 12536 KB correct
8 Correct 241 ms 12408 KB correct
9 Correct 245 ms 12540 KB correct
10 Correct 245 ms 12408 KB correct
11 Correct 245 ms 12412 KB correct
12 Correct 246 ms 12408 KB correct
13 Correct 5 ms 6528 KB correct
14 Correct 244 ms 12408 KB correct
15 Correct 248 ms 12536 KB correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB correct
2 Correct 5 ms 6528 KB correct
3 Correct 5 ms 6528 KB correct
4 Correct 5 ms 6528 KB correct
5 Correct 5 ms 6528 KB correct
6 Correct 4 ms 6528 KB correct
7 Correct 5 ms 6528 KB correct
8 Correct 5 ms 6560 KB correct
9 Correct 5 ms 6528 KB correct
10 Correct 5 ms 6528 KB correct
11 Correct 5 ms 6528 KB correct
12 Correct 5 ms 6528 KB correct
13 Correct 5 ms 6528 KB correct
14 Correct 7 ms 6784 KB correct
15 Correct 8 ms 6784 KB correct
16 Correct 7 ms 6784 KB correct
17 Correct 7 ms 6528 KB correct
18 Correct 6 ms 6528 KB correct
19 Correct 7 ms 6528 KB correct
20 Correct 7 ms 6528 KB correct
21 Correct 6 ms 6528 KB correct
22 Correct 6 ms 6528 KB correct
23 Correct 6 ms 6528 KB correct
24 Correct 6 ms 6528 KB correct
25 Correct 5 ms 6528 KB correct
26 Correct 6 ms 6528 KB correct
27 Correct 6 ms 6528 KB correct
28 Correct 5 ms 6528 KB correct
29 Correct 5 ms 6528 KB correct
30 Correct 6 ms 6528 KB correct
31 Correct 6 ms 6528 KB correct
32 Correct 6 ms 6528 KB correct
33 Correct 6 ms 6528 KB correct
34 Correct 58 ms 8184 KB correct
35 Correct 262 ms 7640 KB correct
36 Correct 183 ms 7160 KB correct
37 Correct 17 ms 6528 KB correct
38 Correct 263 ms 7544 KB correct
39 Correct 239 ms 7288 KB correct
40 Correct 177 ms 7160 KB correct
41 Correct 62 ms 8088 KB correct
42 Correct 271 ms 7492 KB correct
43 Correct 134 ms 7040 KB correct
44 Correct 113 ms 7032 KB correct
45 Correct 131 ms 7012 KB correct
46 Correct 101 ms 6784 KB correct
47 Correct 45 ms 6656 KB correct
48 Correct 8 ms 6528 KB correct
49 Correct 16 ms 6528 KB correct
50 Correct 46 ms 6656 KB correct
51 Correct 134 ms 7032 KB correct
52 Correct 113 ms 7032 KB correct
53 Correct 106 ms 6904 KB correct
54 Correct 146 ms 7160 KB correct
55 Correct 120 ms 7160 KB correct
56 Correct 117 ms 7080 KB correct
57 Correct 115 ms 7032 KB correct
58 Correct 5 ms 6528 KB correct
59 Correct 5 ms 6528 KB correct
60 Correct 160 ms 9984 KB correct
61 Correct 243 ms 12408 KB correct
62 Correct 250 ms 12488 KB correct
63 Correct 248 ms 12452 KB correct
64 Correct 251 ms 12536 KB correct
65 Correct 241 ms 12408 KB correct
66 Correct 245 ms 12540 KB correct
67 Correct 245 ms 12408 KB correct
68 Correct 245 ms 12412 KB correct
69 Correct 246 ms 12408 KB correct
70 Correct 5 ms 6528 KB correct
71 Correct 244 ms 12408 KB correct
72 Correct 248 ms 12536 KB correct
73 Correct 5 ms 6528 KB correct
74 Incorrect 187 ms 12408 KB WA in grader: NO
75 Halted 0 ms 0 KB -