답안 #407547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407547	2021-05-19T02:29:07 Z	Kevin_Zhang_TW	Simurgh (IOI17_simurgh)	C++17	51 / 100	279 ms	12508 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);
	}

	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:120:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  120 |  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	3 ms	460 KB	correct
18	Correct	2 ms	332 KB	correct
19	Correct	4 ms	460 KB	correct
20	Correct	3 ms	332 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	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	204 KB	correct
30	Correct	2 ms	332 KB	correct
31	Correct	3 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	3 ms	460 KB	correct
18	Correct	2 ms	332 KB	correct
19	Correct	4 ms	460 KB	correct
20	Correct	3 ms	332 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	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	204 KB	correct
30	Correct	2 ms	332 KB	correct
31	Correct	3 ms	332 KB	correct
32	Correct	2 ms	332 KB	correct
33	Correct	2 ms	332 KB	correct
34	Correct	279 ms	4680 KB	correct
35	Correct	250 ms	4532 KB	correct
36	Correct	170 ms	3144 KB	correct
37	Correct	10 ms	500 KB	correct
38	Correct	263 ms	4676 KB	correct
39	Correct	218 ms	4012 KB	correct
40	Correct	174 ms	3268 KB	correct
41	Correct	265 ms	4660 KB	correct
42	Correct	260 ms	4556 KB	correct
43	Correct	117 ms	2764 KB	correct
44	Correct	94 ms	2284 KB	correct
45	Correct	115 ms	2608 KB	correct
46	Correct	81 ms	1944 KB	correct
47	Correct	32 ms	972 KB	correct
48	Correct	3 ms	332 KB	correct
49	Correct	10 ms	460 KB	correct
50	Correct	33 ms	1032 KB	correct
51	Correct	118 ms	2608 KB	correct
52	Correct	96 ms	2296 KB	correct
53	Correct	87 ms	1988 KB	correct
54	Correct	122 ms	2756 KB	correct
55	Correct	117 ms	2620 KB	correct
56	Correct	115 ms	2764 KB	correct
57	Correct	118 ms	2636 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	268 ms	12508 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	3 ms	460 KB	correct
18	Correct	2 ms	332 KB	correct
19	Correct	4 ms	460 KB	correct
20	Correct	3 ms	332 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	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	204 KB	correct
30	Correct	2 ms	332 KB	correct
31	Correct	3 ms	332 KB	correct
32	Correct	2 ms	332 KB	correct
33	Correct	2 ms	332 KB	correct
34	Correct	279 ms	4680 KB	correct
35	Correct	250 ms	4532 KB	correct
36	Correct	170 ms	3144 KB	correct
37	Correct	10 ms	500 KB	correct
38	Correct	263 ms	4676 KB	correct
39	Correct	218 ms	4012 KB	correct
40	Correct	174 ms	3268 KB	correct
41	Correct	265 ms	4660 KB	correct
42	Correct	260 ms	4556 KB	correct
43	Correct	117 ms	2764 KB	correct
44	Correct	94 ms	2284 KB	correct
45	Correct	115 ms	2608 KB	correct
46	Correct	81 ms	1944 KB	correct
47	Correct	32 ms	972 KB	correct
48	Correct	3 ms	332 KB	correct
49	Correct	10 ms	460 KB	correct
50	Correct	33 ms	1032 KB	correct
51	Correct	118 ms	2608 KB	correct
52	Correct	96 ms	2296 KB	correct
53	Correct	87 ms	1988 KB	correct
54	Correct	122 ms	2756 KB	correct
55	Correct	117 ms	2620 KB	correct
56	Correct	115 ms	2764 KB	correct
57	Correct	118 ms	2636 KB	correct
58	Correct	1 ms	204 KB	correct
59	Correct	1 ms	204 KB	correct
60	Incorrect	268 ms	12508 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #407547

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