답안 #407553

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407553	2021-05-19T02:44:26 Z	Kevin_Zhang_TW	Simurgh (IOI17_simurgh)	C++17	51 / 100	287 ms	12512 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) {

	int m = u.size();

	vector<int> old, on_tree(m), cnt(n);
	{
		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, node;
		while (a != b) {
			if (dep[a] < dep[b]) swap(a, b);
			all.pb( id[ {a, pa[a]} ] );
			node.pb(a);
			a = pa[a];
		}

		for (int u : node) ++cnt[u];

		for (int j : all) {
			if (D.S(O) == n) break;
			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 = 1;i < n;++i) if (cnt[i] == 0)
		D.M( id[{i, pa[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:122:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  122 |  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	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	204 KB	correct
12	Correct	1 ms	204 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	460 KB	correct
17	Correct	4 ms	332 KB	correct
18	Correct	2 ms	332 KB	correct
19	Correct	4 ms	460 KB	correct
20	Correct	4 ms	332 KB	correct
21	Correct	3 ms	332 KB	correct
22	Correct	3 ms	332 KB	correct
23	Correct	2 ms	332 KB	correct
24	Correct	2 ms	332 KB	correct
25	Correct	1 ms	204 KB	correct
26	Correct	2 ms	332 KB	correct
27	Correct	2 ms	332 KB	correct
28	Correct	1 ms	332 KB	correct
29	Correct	1 ms	332 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	204 KB	correct
14	Correct	4 ms	460 KB	correct
15	Correct	4 ms	460 KB	correct
16	Correct	4 ms	460 KB	correct
17	Correct	4 ms	332 KB	correct
18	Correct	2 ms	332 KB	correct
19	Correct	4 ms	460 KB	correct
20	Correct	4 ms	332 KB	correct
21	Correct	3 ms	332 KB	correct
22	Correct	3 ms	332 KB	correct
23	Correct	2 ms	332 KB	correct
24	Correct	2 ms	332 KB	correct
25	Correct	1 ms	204 KB	correct
26	Correct	2 ms	332 KB	correct
27	Correct	2 ms	332 KB	correct
28	Correct	1 ms	332 KB	correct
29	Correct	1 ms	332 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	281 ms	4692 KB	correct
35	Correct	267 ms	4420 KB	correct
36	Correct	180 ms	3200 KB	correct
37	Correct	10 ms	460 KB	correct
38	Correct	274 ms	4648 KB	correct
39	Correct	227 ms	4008 KB	correct
40	Correct	187 ms	3204 KB	correct
41	Correct	287 ms	4680 KB	correct
42	Correct	274 ms	4676 KB	correct
43	Correct	124 ms	2740 KB	correct
44	Correct	101 ms	2244 KB	correct
45	Correct	120 ms	2620 KB	correct
46	Correct	83 ms	1932 KB	correct
47	Correct	33 ms	972 KB	correct
48	Correct	3 ms	332 KB	correct
49	Correct	9 ms	460 KB	correct
50	Correct	28 ms	1024 KB	correct
51	Correct	115 ms	2680 KB	correct
52	Correct	91 ms	2244 KB	correct
53	Correct	73 ms	1944 KB	correct
54	Correct	123 ms	2744 KB	correct
55	Correct	57 ms	2508 KB	correct
56	Correct	49 ms	2508 KB	correct
57	Correct	53 ms	2508 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	266 ms	12512 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	204 KB	correct
14	Correct	4 ms	460 KB	correct
15	Correct	4 ms	460 KB	correct
16	Correct	4 ms	460 KB	correct
17	Correct	4 ms	332 KB	correct
18	Correct	2 ms	332 KB	correct
19	Correct	4 ms	460 KB	correct
20	Correct	4 ms	332 KB	correct
21	Correct	3 ms	332 KB	correct
22	Correct	3 ms	332 KB	correct
23	Correct	2 ms	332 KB	correct
24	Correct	2 ms	332 KB	correct
25	Correct	1 ms	204 KB	correct
26	Correct	2 ms	332 KB	correct
27	Correct	2 ms	332 KB	correct
28	Correct	1 ms	332 KB	correct
29	Correct	1 ms	332 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	281 ms	4692 KB	correct
35	Correct	267 ms	4420 KB	correct
36	Correct	180 ms	3200 KB	correct
37	Correct	10 ms	460 KB	correct
38	Correct	274 ms	4648 KB	correct
39	Correct	227 ms	4008 KB	correct
40	Correct	187 ms	3204 KB	correct
41	Correct	287 ms	4680 KB	correct
42	Correct	274 ms	4676 KB	correct
43	Correct	124 ms	2740 KB	correct
44	Correct	101 ms	2244 KB	correct
45	Correct	120 ms	2620 KB	correct
46	Correct	83 ms	1932 KB	correct
47	Correct	33 ms	972 KB	correct
48	Correct	3 ms	332 KB	correct
49	Correct	9 ms	460 KB	correct
50	Correct	28 ms	1024 KB	correct
51	Correct	115 ms	2680 KB	correct
52	Correct	91 ms	2244 KB	correct
53	Correct	73 ms	1944 KB	correct
54	Correct	123 ms	2744 KB	correct
55	Correct	57 ms	2508 KB	correct
56	Correct	49 ms	2508 KB	correct
57	Correct	53 ms	2508 KB	correct
58	Correct	1 ms	204 KB	correct
59	Correct	1 ms	204 KB	correct
60	Incorrect	266 ms	12512 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #407553

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