답안 #832490

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832490	2023-08-21T10:52:20 Z	MadokaMagicaFan	Simurgh (IOI17_simurgh)	C++14	51 / 100	195 ms	2188 KB

simurgh

#include "bits/stdc++.h"
#include "simurgh.h"
using namespace std;
using ll = long long;
#define pb push_back
#define sz(v) ((int)v.size())

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int p[500];
int getp(int x) { return p[x] = (x == p[x] ? x : getp(p[x])); }
int uni(int a, int b) {
	a = getp(a);
	b = getp(b);
	if (a == b) return 0;
	p[a] = b;
	return 1;
}

vector<int>
find_roads(int n, vector<int> u, vector<int> v) {
	int m = sz(u);
	vector<int> ans, r, us(m, 0), z, order(m);
	iota(order.begin(), order.end(), 0);
	shuffle(order.begin(), order.end(), rng);
	for (int i = 0; i < n-1; ++i) {
		for (int i = 0; i < n; ++i) p[i] = i;
		int c = 0;
		shuffle(order.begin(), order.end(), rng);
		if (sz(ans) == n-1) break;
		r = ans;
		for (auto x : ans) {
			c += uni(u[x], v[x]);
		}

		int p = 0;
		while (c < n-2) {
			if (uni(u[order[p]], v[order[p]])) {
				++c;
				r.pb(order[p]);
			}
			++p;
		}

		while (us[order[p]] || getp(u[order[p]]) == getp(v[order[p]]))
			++p;
		r.pb(order[p]);
		z.clear();
		z.pb(order[p]);
		assert(sz(r) == n-1);
		int x = count_common_roads(r);

		for (int j = p+1; j < m; ++j) {
			if(us[order[j]]) continue;
			if (getp(u[order[j]]) == getp(v[order[j]])) continue;
			r[n-2] = order[j];
			us[order[j]] = 1;
			int l = count_common_roads(r);
			if (l == x) {
				z.pb(order[j]);
			} else if (l < x) {
				break;
			} else if (l > x) {
				z.clear(); z.pb(order[j]);
				break;
			}
		}

		for (auto j : z)
			ans.pb(j);
	}

	return ans;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	0 ms	212 KB	correct
4	Correct	0 ms	292 KB	correct
5	Correct	0 ms	212 KB	correct
6	Correct	0 ms	212 KB	correct
7	Correct	0 ms	212 KB	correct
8	Correct	0 ms	212 KB	correct
9	Correct	0 ms	212 KB	correct
10	Correct	0 ms	212 KB	correct
11	Correct	0 ms	212 KB	correct
12	Correct	0 ms	212 KB	correct
13	Correct	0 ms	212 KB	correct
14	Correct	2 ms	212 KB	correct
15	Correct	2 ms	212 KB	correct
16	Correct	2 ms	340 KB	correct
17	Correct	2 ms	212 KB	correct
18	Correct	1 ms	212 KB	correct
19	Correct	2 ms	212 KB	correct
20	Correct	2 ms	212 KB	correct
21	Correct	2 ms	212 KB	correct
22	Correct	1 ms	212 KB	correct
23	Correct	1 ms	212 KB	correct
24	Correct	1 ms	212 KB	correct
25	Correct	1 ms	212 KB	correct
26	Correct	1 ms	212 KB	correct
27	Correct	1 ms	212 KB	correct
28	Correct	1 ms	212 KB	correct
29	Correct	1 ms	212 KB	correct
30	Correct	1 ms	212 KB	correct
31	Correct	1 ms	212 KB	correct
32	Correct	1 ms	212 KB	correct
33	Correct	1 ms	212 KB	correct
34	Correct	173 ms	980 KB	correct
35	Correct	161 ms	940 KB	correct
36	Correct	111 ms	744 KB	correct
37	Correct	10 ms	212 KB	correct
38	Correct	161 ms	960 KB	correct
39	Correct	149 ms	852 KB	correct
40	Correct	117 ms	744 KB	correct
41	Correct	174 ms	1040 KB	correct
42	Correct	173 ms	964 KB	correct
43	Correct	89 ms	644 KB	correct
44	Correct	70 ms	572 KB	correct
45	Correct	82 ms	596 KB	correct
46	Correct	61 ms	468 KB	correct
47	Correct	28 ms	420 KB	correct
48	Correct	5 ms	212 KB	correct
49	Correct	10 ms	336 KB	correct
50	Correct	29 ms	412 KB	correct
51	Correct	83 ms	544 KB	correct
52	Correct	71 ms	576 KB	correct
53	Correct	62 ms	536 KB	correct
54	Correct	84 ms	596 KB	correct
55	Correct	83 ms	596 KB	correct
56	Correct	83 ms	632 KB	correct
57	Correct	93 ms	632 KB	correct

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	0 ms	212 KB	correct
4	Correct	0 ms	292 KB	correct
5	Correct	0 ms	212 KB	correct
6	Correct	0 ms	212 KB	correct
7	Correct	0 ms	212 KB	correct
8	Correct	0 ms	212 KB	correct
9	Correct	0 ms	212 KB	correct
10	Correct	0 ms	212 KB	correct
11	Correct	0 ms	212 KB	correct
12	Correct	0 ms	212 KB	correct
13	Correct	0 ms	212 KB	correct
14	Correct	2 ms	212 KB	correct
15	Correct	2 ms	212 KB	correct
16	Correct	2 ms	340 KB	correct
17	Correct	2 ms	212 KB	correct
18	Correct	1 ms	212 KB	correct
19	Correct	2 ms	212 KB	correct
20	Correct	2 ms	212 KB	correct
21	Correct	2 ms	212 KB	correct
22	Correct	1 ms	212 KB	correct
23	Correct	1 ms	212 KB	correct
24	Correct	1 ms	212 KB	correct
25	Correct	1 ms	212 KB	correct
26	Correct	1 ms	212 KB	correct
27	Correct	1 ms	212 KB	correct
28	Correct	1 ms	212 KB	correct
29	Correct	1 ms	212 KB	correct
30	Correct	1 ms	212 KB	correct
31	Correct	1 ms	212 KB	correct
32	Correct	1 ms	212 KB	correct
33	Correct	1 ms	212 KB	correct
34	Correct	173 ms	980 KB	correct
35	Correct	161 ms	940 KB	correct
36	Correct	111 ms	744 KB	correct
37	Correct	10 ms	212 KB	correct
38	Correct	161 ms	960 KB	correct
39	Correct	149 ms	852 KB	correct
40	Correct	117 ms	744 KB	correct
41	Correct	174 ms	1040 KB	correct
42	Correct	173 ms	964 KB	correct
43	Correct	89 ms	644 KB	correct
44	Correct	70 ms	572 KB	correct
45	Correct	82 ms	596 KB	correct
46	Correct	61 ms	468 KB	correct
47	Correct	28 ms	420 KB	correct
48	Correct	5 ms	212 KB	correct
49	Correct	10 ms	336 KB	correct
50	Correct	29 ms	412 KB	correct
51	Correct	83 ms	544 KB	correct
52	Correct	71 ms	576 KB	correct
53	Correct	62 ms	536 KB	correct
54	Correct	84 ms	596 KB	correct
55	Correct	83 ms	596 KB	correct
56	Correct	83 ms	632 KB	correct
57	Correct	93 ms	632 KB	correct
58	Correct	0 ms	212 KB	correct
59	Correct	0 ms	212 KB	correct
60	Incorrect	195 ms	2188 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #832490

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