답안 #300785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
300785	2020-09-17T13:29:04 Z	JPN20	Simurgh (IOI17_simurgh)	C++17	51 / 100	266 ms	9472 KB

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.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	6528 KB	correct
2	Correct	5 ms	6432 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	5 ms	6528 KB	correct
7	Correct	5 ms	6528 KB	correct
8	Correct	5 ms	6528 KB	correct
9	Correct	5 ms	6460 KB	correct
10	Correct	5 ms	6528 KB	correct
11	Correct	6 ms	6560 KB	correct
12	Correct	5 ms	6528 KB	correct
13	Correct	5 ms	6528 KB	correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	6528 KB	correct
2	Correct	5 ms	6432 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	5 ms	6528 KB	correct
7	Correct	5 ms	6528 KB	correct
8	Correct	5 ms	6528 KB	correct
9	Correct	5 ms	6460 KB	correct
10	Correct	5 ms	6528 KB	correct
11	Correct	6 ms	6560 KB	correct
12	Correct	5 ms	6528 KB	correct
13	Correct	5 ms	6528 KB	correct
14	Correct	8 ms	6528 KB	correct
15	Correct	8 ms	6528 KB	correct
16	Correct	8 ms	6528 KB	correct
17	Correct	7 ms	6528 KB	correct
18	Correct	6 ms	6528 KB	correct
19	Correct	9 ms	6528 KB	correct
20	Correct	7 ms	6528 KB	correct
21	Correct	9 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	7 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	9 ms	6528 KB	correct
33	Correct	6 ms	6528 KB	correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	6528 KB	correct
2	Correct	5 ms	6432 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	5 ms	6528 KB	correct
7	Correct	5 ms	6528 KB	correct
8	Correct	5 ms	6528 KB	correct
9	Correct	5 ms	6460 KB	correct
10	Correct	5 ms	6528 KB	correct
11	Correct	6 ms	6560 KB	correct
12	Correct	5 ms	6528 KB	correct
13	Correct	5 ms	6528 KB	correct
14	Correct	8 ms	6528 KB	correct
15	Correct	8 ms	6528 KB	correct
16	Correct	8 ms	6528 KB	correct
17	Correct	7 ms	6528 KB	correct
18	Correct	6 ms	6528 KB	correct
19	Correct	9 ms	6528 KB	correct
20	Correct	7 ms	6528 KB	correct
21	Correct	9 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	7 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	9 ms	6528 KB	correct
33	Correct	6 ms	6528 KB	correct
34	Correct	258 ms	7552 KB	correct
35	Correct	258 ms	7672 KB	correct
36	Correct	177 ms	7416 KB	correct
37	Correct	17 ms	6528 KB	correct
38	Correct	254 ms	7672 KB	correct
39	Correct	231 ms	7416 KB	correct
40	Correct	173 ms	7288 KB	correct
41	Correct	263 ms	7672 KB	correct
42	Correct	266 ms	7564 KB	correct
43	Correct	132 ms	7176 KB	correct
44	Correct	116 ms	7160 KB	correct
45	Correct	129 ms	7040 KB	correct
46	Correct	115 ms	6912 KB	correct
47	Correct	44 ms	6656 KB	correct
48	Correct	8 ms	6528 KB	correct
49	Correct	16 ms	6528 KB	correct
50	Correct	44 ms	6656 KB	correct
51	Correct	135 ms	7160 KB	correct
52	Correct	111 ms	6912 KB	correct
53	Correct	102 ms	7032 KB	correct
54	Correct	135 ms	7240 KB	correct
55	Correct	116 ms	7160 KB	correct
56	Correct	114 ms	7040 KB	correct
57	Correct	113 ms	7040 KB	correct

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	6528 KB	correct
2	Correct	5 ms	6528 KB	correct
3	Incorrect	192 ms	9472 KB	WA in grader: NO
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	6528 KB	correct
2	Correct	5 ms	6432 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	5 ms	6528 KB	correct
7	Correct	5 ms	6528 KB	correct
8	Correct	5 ms	6528 KB	correct
9	Correct	5 ms	6460 KB	correct
10	Correct	5 ms	6528 KB	correct
11	Correct	6 ms	6560 KB	correct
12	Correct	5 ms	6528 KB	correct
13	Correct	5 ms	6528 KB	correct
14	Correct	8 ms	6528 KB	correct
15	Correct	8 ms	6528 KB	correct
16	Correct	8 ms	6528 KB	correct
17	Correct	7 ms	6528 KB	correct
18	Correct	6 ms	6528 KB	correct
19	Correct	9 ms	6528 KB	correct
20	Correct	7 ms	6528 KB	correct
21	Correct	9 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	7 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	9 ms	6528 KB	correct
33	Correct	6 ms	6528 KB	correct
34	Correct	258 ms	7552 KB	correct
35	Correct	258 ms	7672 KB	correct
36	Correct	177 ms	7416 KB	correct
37	Correct	17 ms	6528 KB	correct
38	Correct	254 ms	7672 KB	correct
39	Correct	231 ms	7416 KB	correct
40	Correct	173 ms	7288 KB	correct
41	Correct	263 ms	7672 KB	correct
42	Correct	266 ms	7564 KB	correct
43	Correct	132 ms	7176 KB	correct
44	Correct	116 ms	7160 KB	correct
45	Correct	129 ms	7040 KB	correct
46	Correct	115 ms	6912 KB	correct
47	Correct	44 ms	6656 KB	correct
48	Correct	8 ms	6528 KB	correct
49	Correct	16 ms	6528 KB	correct
50	Correct	44 ms	6656 KB	correct
51	Correct	135 ms	7160 KB	correct
52	Correct	111 ms	6912 KB	correct
53	Correct	102 ms	7032 KB	correct
54	Correct	135 ms	7240 KB	correct
55	Correct	116 ms	7160 KB	correct
56	Correct	114 ms	7040 KB	correct
57	Correct	113 ms	7040 KB	correct
58	Correct	5 ms	6528 KB	correct
59	Correct	5 ms	6528 KB	correct
60	Incorrect	192 ms	9472 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #300785

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 19.0

Subtask #5 0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 30.0