oj.uz

답안 #767690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
767690 2023-06-27T04:29:12 Z SanguineChameleon Simurgh (IOI17_simurgh) C++17
30 / 100
 63 ms 4340 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e2 + 20;
const int maxm = maxn * maxn / 2;
vector<pair<int, int>> adj[maxn];
bool tree[maxm];
int flag[maxm];
int comp[maxn];

void dfs1(int u) {
	flag[u] = true;
	for (auto e: adj[u]) {
		int v = e.first;
		int id = e.second;
		if (!flag[v]) {
			tree[id] = true;
			dfs1(v);
		}
	}
}

void dfs2(int u, int p) {
	comp[u] = 1;
	for (auto e: adj[u]) {
		int v = e.first;
		int id = e.second;
		if (tree[id] && v != p) {
			dfs2(v, u);
		}
	}
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	int m = u.size();
	for (int i = 0; i < m; i++) {
		adj[u[i]].emplace_back(v[i], i);
		adj[v[i]].emplace_back(u[i], i);
	}
	dfs1(0);
	for (int i = 0; i < m; i++) {
		flag[i] = -1;
	}
	vector<int> res;
	for (int i = 0; i < m; i++) {
		if (tree[i]) {
			res.push_back(i);
		}
	}
	while (true) {
		for (int i = 0; i < n - 1; i++) {
			if (flag[res[i]] == -1) {
				tree[res[i]] = false;
				res.erase(res.begin() + i);
				break;
			}
		}
		if ((int)res.size() == n - 1) {
			break;
		}
		for (int i = 0; i < n; i++) {
			comp[i] = 0;
		}
		dfs2(0, -1);
		pair<int, int> mx = make_pair(-1, -1);
		for (int i = 0; i < m; i++) {
			if (comp[u[i]] != comp[v[i]]) {
				res.push_back(i);
				int cnt = count_common_roads(res);
				if (cnt > mx.first) {
					if (mx.second != -1) {
						flag[mx.second] = 0;
					}
					flag[i] = 1;
					mx = make_pair(cnt, i);
				}
				res.pop_back();
			}
		}
		tree[mx.second] = true;
		res.push_back(mx.second);
	}
	return res;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 224 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 1 ms 320 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 212 KB correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 224 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 1 ms 320 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 6 ms 340 KB correct
15 Correct 3 ms 340 KB correct
16 Correct 4 ms 328 KB correct
17 Correct 4 ms 340 KB correct
18 Correct 2 ms 328 KB correct
19 Correct 6 ms 340 KB correct
20 Correct 5 ms 340 KB correct
21 Correct 4 ms 340 KB correct
22 Correct 3 ms 340 KB correct
23 Correct 2 ms 340 KB correct
24 Correct 2 ms 340 KB correct
25 Correct 1 ms 324 KB correct
26 Correct 2 ms 340 KB correct
27 Correct 3 ms 320 KB correct
28 Correct 1 ms 324 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 6 ms 340 KB correct
31 Correct 4 ms 340 KB correct
32 Correct 4 ms 340 KB correct
33 Correct 4 ms 340 KB correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 224 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 1 ms 320 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 6 ms 340 KB correct
15 Correct 3 ms 340 KB correct
16 Correct 4 ms 328 KB correct
17 Correct 4 ms 340 KB correct
18 Correct 2 ms 328 KB correct
19 Correct 6 ms 340 KB correct
20 Correct 5 ms 340 KB correct
21 Correct 4 ms 340 KB correct
22 Correct 3 ms 340 KB correct
23 Correct 2 ms 340 KB correct
24 Correct 2 ms 340 KB correct
25 Correct 1 ms 324 KB correct
26 Correct 2 ms 340 KB correct
27 Correct 3 ms 320 KB correct
28 Correct 1 ms 324 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 6 ms 340 KB correct
31 Correct 4 ms 340 KB correct
32 Correct 4 ms 340 KB correct
33 Correct 4 ms 340 KB correct
34 Incorrect 63 ms 1676 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Correct 1 ms 212 KB correct
4 Correct 1 ms 212 KB correct
5 Correct 1 ms 224 KB correct
6 Correct 1 ms 212 KB correct
7 Correct 1 ms 320 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 212 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 212 KB correct
14 Correct 6 ms 340 KB correct
15 Correct 3 ms 340 KB correct
16 Correct 4 ms 328 KB correct
17 Correct 4 ms 340 KB correct
18 Correct 2 ms 328 KB correct
19 Correct 6 ms 340 KB correct
20 Correct 5 ms 340 KB correct
21 Correct 4 ms 340 KB correct
22 Correct 3 ms 340 KB correct
23 Correct 2 ms 340 KB correct
24 Correct 2 ms 340 KB correct
25 Correct 1 ms 324 KB correct
26 Correct 2 ms 340 KB correct
27 Correct 3 ms 320 KB correct
28 Correct 1 ms 324 KB correct
29 Correct 1 ms 212 KB correct
30 Correct 6 ms 340 KB correct
31 Correct 4 ms 340 KB correct
32 Correct 4 ms 340 KB correct
33 Correct 4 ms 340 KB correct
34 Incorrect 63 ms 1676 KB WA in grader: NO
35 Halted 0 ms 0 KB -