답안 #407546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407546	2021-05-19T02:28:17 Z	Kevin_Zhang_TW	Simurgh (IOI17_simurgh)	C++17	51 / 100	276 ms	13100 KB

simurgh

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 505;

#include "simurgh.h"

map< pair<int,int>, int > id;

int qry(const vector<int> &r) { return count_common_roads(r); }

int pa[MAX_N], dep[MAX_N];

vector<int> edge[MAX_N];

struct dsu {
	vector<int> g, sz;
	dsu (int n) { g.resize(n+10), sz.resize(n+10, 1), iota(AI(g), 0); }
	int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); }
	int S(int i) { return sz[ F(i) ]; }
	bool M(int a, int b) { 
		a = F(a), b = F(b);
		if (a == b) return false;
		return sz[a] += sz[b], g[b] = a, true;
	}
};

void dfs(int x, int lst) {
	pa[x] = lst;
	for (int u : edge[x]) if (u != lst) {
		dep[u] = dep[x] + 1;
		dfs(u, x);
	}
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	id.clear();
	for (int i = 0;i < n;++i)
		edge[i].clear();

	int m = u.size();

	vector<int> old, on_tree(m);
	{
		dsu D(n); 

		for (int i = 0;i < m;++i) {
			id[ {u[i], v[i]} ] = i;
			id[ {v[i], u[i]} ] = i;
			if (D.M(v[i], u[i])) {
				edge[ u[i] ].pb( v[i] );
				edge[ v[i] ].pb( u[i] );
				old.pb(i);
				on_tree[i] = true;
			}
		}
	}
	dfs(0, 0);

	int old_val = qry(old);

	dsu D(m + 2);
	int Z = m, O = m+1;

	auto sure = [&](int a) { 
		return D.F(a) == D.F(Z) || D.F(a) == D.F(O);
	};

	for (int i = 0;i < m;++i) {
		if (on_tree[i]) continue;

		int a = u[i], b = v[i];
		vector<int> all;
		while (a != b) {
			if (dep[a] < dep[b]) swap(a, b);
			all.pb( id[ {a, pa[a]} ] );
			a = pa[a];
		}

		for (int j : all) {
			if (sure(i) && sure(j)) continue;
			if (D.F(i) == D.F(j)) continue;
			vector<int> now = old;
			now.erase(find(AI(now), j));
			now.pb(i);

			int nv = qry(now);

			if (nv == old_val) D.M(i, j);
			if (nv > old_val) D.M(i, O), D.M(j, Z);
			if (nv < old_val) D.M(i, Z), D.M(j, O);

		}

	}

	for (int i = 0;i < m;++i) if (D.S(i) == 1)
		D.M(i, O);

	vector<int> res;
	for (int i = 0;i < m;++i) {
		if (D.F(i) == D.F(O))
			res.pb(i);
	}

	return res;

	
}

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	correct
2	Correct	1 ms	204 KB	correct
3	Correct	1 ms	204 KB	correct
4	Correct	1 ms	204 KB	correct
5	Correct	1 ms	204 KB	correct
6	Correct	1 ms	204 KB	correct
7	Correct	1 ms	204 KB	correct
8	Correct	1 ms	204 KB	correct
9	Correct	1 ms	204 KB	correct
10	Correct	1 ms	204 KB	correct
11	Correct	1 ms	304 KB	correct
12	Correct	1 ms	304 KB	correct
13	Correct	1 ms	204 KB	correct
14	Correct	4 ms	460 KB	correct
15	Correct	4 ms	460 KB	correct
16	Correct	4 ms	504 KB	correct
17	Correct	3 ms	460 KB	correct
18	Correct	2 ms	332 KB	correct
19	Correct	4 ms	460 KB	correct
20	Correct	4 ms	440 KB	correct
21	Correct	3 ms	432 KB	correct
22	Correct	3 ms	300 KB	correct
23	Correct	2 ms	296 KB	correct
24	Correct	3 ms	332 KB	correct
25	Correct	1 ms	204 KB	correct
26	Correct	3 ms	332 KB	correct
27	Correct	2 ms	300 KB	correct
28	Correct	1 ms	332 KB	correct
29	Correct	1 ms	332 KB	correct
30	Correct	3 ms	288 KB	correct
31	Correct	3 ms	332 KB	correct
32	Correct	3 ms	404 KB	correct
33	Correct	2 ms	332 KB	correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	correct
2	Correct	1 ms	204 KB	correct
3	Correct	1 ms	204 KB	correct
4	Correct	1 ms	204 KB	correct
5	Correct	1 ms	204 KB	correct
6	Correct	1 ms	204 KB	correct
7	Correct	1 ms	204 KB	correct
8	Correct	1 ms	204 KB	correct
9	Correct	1 ms	204 KB	correct
10	Correct	1 ms	204 KB	correct
11	Correct	1 ms	304 KB	correct
12	Correct	1 ms	304 KB	correct
13	Correct	1 ms	204 KB	correct
14	Correct	4 ms	460 KB	correct
15	Correct	4 ms	460 KB	correct
16	Correct	4 ms	504 KB	correct
17	Correct	3 ms	460 KB	correct
18	Correct	2 ms	332 KB	correct
19	Correct	4 ms	460 KB	correct
20	Correct	4 ms	440 KB	correct
21	Correct	3 ms	432 KB	correct
22	Correct	3 ms	300 KB	correct
23	Correct	2 ms	296 KB	correct
24	Correct	3 ms	332 KB	correct
25	Correct	1 ms	204 KB	correct
26	Correct	3 ms	332 KB	correct
27	Correct	2 ms	300 KB	correct
28	Correct	1 ms	332 KB	correct
29	Correct	1 ms	332 KB	correct
30	Correct	3 ms	288 KB	correct
31	Correct	3 ms	332 KB	correct
32	Correct	3 ms	404 KB	correct
33	Correct	2 ms	332 KB	correct
34	Correct	269 ms	4880 KB	correct
35	Correct	251 ms	4684 KB	correct
36	Correct	170 ms	3300 KB	correct
37	Correct	10 ms	460 KB	correct
38	Correct	263 ms	4852 KB	correct
39	Correct	222 ms	4164 KB	correct
40	Correct	172 ms	3396 KB	correct
41	Correct	267 ms	4880 KB	correct
42	Correct	261 ms	4868 KB	correct
43	Correct	118 ms	2860 KB	correct
44	Correct	93 ms	2372 KB	correct
45	Correct	112 ms	2628 KB	correct
46	Correct	81 ms	2116 KB	correct
47	Correct	32 ms	1056 KB	correct
48	Correct	3 ms	376 KB	correct
49	Correct	9 ms	536 KB	correct
50	Correct	34 ms	1100 KB	correct
51	Correct	114 ms	2720 KB	correct
52	Correct	95 ms	2372 KB	correct
53	Correct	85 ms	2008 KB	correct
54	Correct	123 ms	2860 KB	correct
55	Correct	117 ms	2736 KB	correct
56	Correct	113 ms	2756 KB	correct
57	Correct	117 ms	2692 KB	correct

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	correct
2	Correct	1 ms	204 KB	correct
3	Correct	1 ms	204 KB	correct
4	Correct	1 ms	204 KB	correct
5	Correct	1 ms	204 KB	correct
6	Correct	1 ms	204 KB	correct
7	Correct	1 ms	204 KB	correct
8	Correct	1 ms	204 KB	correct
9	Correct	1 ms	204 KB	correct
10	Correct	1 ms	204 KB	correct
11	Correct	1 ms	304 KB	correct
12	Correct	1 ms	304 KB	correct
13	Correct	1 ms	204 KB	correct
14	Correct	4 ms	460 KB	correct
15	Correct	4 ms	460 KB	correct
16	Correct	4 ms	504 KB	correct
17	Correct	3 ms	460 KB	correct
18	Correct	2 ms	332 KB	correct
19	Correct	4 ms	460 KB	correct
20	Correct	4 ms	440 KB	correct
21	Correct	3 ms	432 KB	correct
22	Correct	3 ms	300 KB	correct
23	Correct	2 ms	296 KB	correct
24	Correct	3 ms	332 KB	correct
25	Correct	1 ms	204 KB	correct
26	Correct	3 ms	332 KB	correct
27	Correct	2 ms	300 KB	correct
28	Correct	1 ms	332 KB	correct
29	Correct	1 ms	332 KB	correct
30	Correct	3 ms	288 KB	correct
31	Correct	3 ms	332 KB	correct
32	Correct	3 ms	404 KB	correct
33	Correct	2 ms	332 KB	correct
34	Correct	269 ms	4880 KB	correct
35	Correct	251 ms	4684 KB	correct
36	Correct	170 ms	3300 KB	correct
37	Correct	10 ms	460 KB	correct
38	Correct	263 ms	4852 KB	correct
39	Correct	222 ms	4164 KB	correct
40	Correct	172 ms	3396 KB	correct
41	Correct	267 ms	4880 KB	correct
42	Correct	261 ms	4868 KB	correct
43	Correct	118 ms	2860 KB	correct
44	Correct	93 ms	2372 KB	correct
45	Correct	112 ms	2628 KB	correct
46	Correct	81 ms	2116 KB	correct
47	Correct	32 ms	1056 KB	correct
48	Correct	3 ms	376 KB	correct
49	Correct	9 ms	536 KB	correct
50	Correct	34 ms	1100 KB	correct
51	Correct	114 ms	2720 KB	correct
52	Correct	95 ms	2372 KB	correct
53	Correct	85 ms	2008 KB	correct
54	Correct	123 ms	2860 KB	correct
55	Correct	117 ms	2736 KB	correct
56	Correct	113 ms	2756 KB	correct
57	Correct	117 ms	2692 KB	correct
58	Correct	1 ms	204 KB	correct
59	Correct	1 ms	204 KB	correct
60	Incorrect	276 ms	13100 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #407546

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