답안 #407548

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407548	2021-05-19T02:30:37 Z	Kevin_Zhang_TW	Simurgh (IOI17_simurgh)	C++17	51 / 100	269 ms	12456 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) {
	static int cnt;
	assert(++cnt == 1);

	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);
	}

	assert(res.size() == n-1);

	return res;

	
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:1:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:119:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |  assert(res.size() == n-1);
      |         ~~~~~~~~~~~^~~~~~

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	204 KB	correct
12	Correct	1 ms	204 KB	correct
13	Correct	1 ms	256 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	204 KB	correct
12	Correct	1 ms	204 KB	correct
13	Correct	1 ms	256 KB	correct
14	Correct	4 ms	460 KB	correct
15	Correct	4 ms	460 KB	correct
16	Correct	4 ms	492 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	3 ms	460 KB	correct
21	Correct	3 ms	332 KB	correct
22	Correct	2 ms	332 KB	correct
23	Correct	2 ms	332 KB	correct
24	Correct	3 ms	332 KB	correct
25	Correct	1 ms	204 KB	correct
26	Correct	2 ms	332 KB	correct
27	Correct	3 ms	332 KB	correct
28	Correct	1 ms	332 KB	correct
29	Correct	2 ms	204 KB	correct
30	Correct	2 ms	332 KB	correct
31	Correct	2 ms	332 KB	correct
32	Correct	2 ms	332 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	204 KB	correct
12	Correct	1 ms	204 KB	correct
13	Correct	1 ms	256 KB	correct
14	Correct	4 ms	460 KB	correct
15	Correct	4 ms	460 KB	correct
16	Correct	4 ms	492 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	3 ms	460 KB	correct
21	Correct	3 ms	332 KB	correct
22	Correct	2 ms	332 KB	correct
23	Correct	2 ms	332 KB	correct
24	Correct	3 ms	332 KB	correct
25	Correct	1 ms	204 KB	correct
26	Correct	2 ms	332 KB	correct
27	Correct	3 ms	332 KB	correct
28	Correct	1 ms	332 KB	correct
29	Correct	2 ms	204 KB	correct
30	Correct	2 ms	332 KB	correct
31	Correct	2 ms	332 KB	correct
32	Correct	2 ms	332 KB	correct
33	Correct	2 ms	332 KB	correct
34	Correct	267 ms	4696 KB	correct
35	Correct	251 ms	4600 KB	correct
36	Correct	170 ms	3208 KB	correct
37	Correct	10 ms	460 KB	correct
38	Correct	267 ms	4588 KB	correct
39	Correct	224 ms	4036 KB	correct
40	Correct	176 ms	3240 KB	correct
41	Correct	266 ms	4680 KB	correct
42	Correct	262 ms	4684 KB	correct
43	Correct	119 ms	2756 KB	correct
44	Correct	94 ms	2256 KB	correct
45	Correct	113 ms	2604 KB	correct
46	Correct	81 ms	2056 KB	correct
47	Correct	32 ms	1028 KB	correct
48	Correct	3 ms	332 KB	correct
49	Correct	9 ms	460 KB	correct
50	Correct	33 ms	1008 KB	correct
51	Correct	112 ms	2608 KB	correct
52	Correct	101 ms	2284 KB	correct
53	Correct	84 ms	1988 KB	correct
54	Correct	121 ms	2748 KB	correct
55	Correct	113 ms	2644 KB	correct
56	Correct	112 ms	2636 KB	correct
57	Correct	119 ms	2640 KB	correct

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	correct
2	Correct	1 ms	204 KB	correct
3	Incorrect	269 ms	12456 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	204 KB	correct
12	Correct	1 ms	204 KB	correct
13	Correct	1 ms	256 KB	correct
14	Correct	4 ms	460 KB	correct
15	Correct	4 ms	460 KB	correct
16	Correct	4 ms	492 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	3 ms	460 KB	correct
21	Correct	3 ms	332 KB	correct
22	Correct	2 ms	332 KB	correct
23	Correct	2 ms	332 KB	correct
24	Correct	3 ms	332 KB	correct
25	Correct	1 ms	204 KB	correct
26	Correct	2 ms	332 KB	correct
27	Correct	3 ms	332 KB	correct
28	Correct	1 ms	332 KB	correct
29	Correct	2 ms	204 KB	correct
30	Correct	2 ms	332 KB	correct
31	Correct	2 ms	332 KB	correct
32	Correct	2 ms	332 KB	correct
33	Correct	2 ms	332 KB	correct
34	Correct	267 ms	4696 KB	correct
35	Correct	251 ms	4600 KB	correct
36	Correct	170 ms	3208 KB	correct
37	Correct	10 ms	460 KB	correct
38	Correct	267 ms	4588 KB	correct
39	Correct	224 ms	4036 KB	correct
40	Correct	176 ms	3240 KB	correct
41	Correct	266 ms	4680 KB	correct
42	Correct	262 ms	4684 KB	correct
43	Correct	119 ms	2756 KB	correct
44	Correct	94 ms	2256 KB	correct
45	Correct	113 ms	2604 KB	correct
46	Correct	81 ms	2056 KB	correct
47	Correct	32 ms	1028 KB	correct
48	Correct	3 ms	332 KB	correct
49	Correct	9 ms	460 KB	correct
50	Correct	33 ms	1008 KB	correct
51	Correct	112 ms	2608 KB	correct
52	Correct	101 ms	2284 KB	correct
53	Correct	84 ms	1988 KB	correct
54	Correct	121 ms	2748 KB	correct
55	Correct	113 ms	2644 KB	correct
56	Correct	112 ms	2636 KB	correct
57	Correct	119 ms	2640 KB	correct
58	Correct	1 ms	332 KB	correct
59	Correct	1 ms	204 KB	correct
60	Incorrect	269 ms	12456 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #407548

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