oj.uz

Submission #137751

# Submission time Handle Problem Language Result Execution time Memory
137751 2019-07-28T09:24:43 Z MAMBA Simurgh (IOI17_simurgh) C++17
30 / 100
 434 ms 3320 KB 
#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define pb push_back

typedef vector<int> vi;

const int N = 510;

struct dsu {
	int par[N];
	dsu() {
		iota(par , par + N, 0);
	}
	int getPar(int v) {
		return v == par[v] ? v : par[v] = getPar(par[v]);
	}
	inline bool merge(int a, int b) {
		if ((a = getPar(a)) == (b = getPar(b))) return false;
		par[a] = b;
		return true;
	}
};

dsu dd;
bitset<N> mark;

vi adj[N];

int dfs(int v) {
	mark[v] =true;
	int res = -1;
	for (auto e : adj[v])
		if (!mark[e]) {
			res = dfs(e);
			break;
		}
	if (res == -1) return v;
	return res;
}

vi find_roads(int n, vi u, vi v) {
	int m = u.size();

	vi local;

	while (local.size() < n - 1) {

		mark.reset();
		rep(i , 0 , n) adj[i].clear();
		rep(i , 0 , m) {
			adj[dd.getPar(u[i])].pb(dd.getPar(v[i]));
			adj[dd.getPar(v[i])].pb(dd.getPar(u[i]));
		}

		int me = dfs(dd.getPar(0));

		dsu ds;
		vi ask = local;
		for (auto e : ask) ds.merge(u[e] , v[e]);
		rep(i , 0 , m) 
			if (ds.getPar(u[i]) != me && ds.getPar(v[i]) != me && ds.merge(u[i] , v[i]))
				ask.pb(i);
		vi A, B;
		rep(i , 0 , m) {
			int a = ds.getPar(u[i]);
			int b = ds.getPar(v[i]);
			if ((a == me && b != me) || (b == me && a != me)) {
				A.pb(i);
				ask.pb(i);
				B.pb(count_common_roads(ask));
				ask.pop_back();
			}
		}
		while (B.empty());
		int res = *max_element(B.begin(), B.end());
		rep(i , 0 , A.size())
			if (B[i] == res) {
				local.pb(A[i]);
				dd.merge(u[A[i]] , v[A[i]]);
			}
	}

	return local;
}

Compilation message

simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (local.size() < n - 1) {
         ~~~~~~~~~~~~~^~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 256 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 408 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 2 ms 376 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 376 KB correct
10 Correct 2 ms 376 KB correct
11 Correct 2 ms 376 KB correct
12 Correct 2 ms 376 KB correct
13 Correct 2 ms 376 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 256 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 408 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 2 ms 376 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 376 KB correct
10 Correct 2 ms 376 KB correct
11 Correct 2 ms 376 KB correct
12 Correct 2 ms 376 KB correct
13 Correct 2 ms 376 KB correct
14 Correct 9 ms 376 KB correct
15 Correct 8 ms 504 KB correct
16 Correct 9 ms 504 KB correct
17 Correct 7 ms 376 KB correct
18 Correct 4 ms 376 KB correct
19 Correct 7 ms 376 KB correct
20 Correct 7 ms 376 KB correct
21 Correct 7 ms 376 KB correct
22 Correct 6 ms 504 KB correct
23 Correct 6 ms 376 KB correct
24 Correct 6 ms 376 KB correct
25 Correct 2 ms 376 KB correct
26 Correct 6 ms 376 KB correct
27 Correct 6 ms 376 KB correct
28 Correct 4 ms 376 KB correct
29 Correct 3 ms 380 KB correct
30 Correct 6 ms 376 KB correct
31 Correct 5 ms 376 KB correct
32 Correct 6 ms 376 KB correct
33 Correct 5 ms 348 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 256 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 408 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 2 ms 376 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 376 KB correct
10 Correct 2 ms 376 KB correct
11 Correct 2 ms 376 KB correct
12 Correct 2 ms 376 KB correct
13 Correct 2 ms 376 KB correct
14 Correct 9 ms 376 KB correct
15 Correct 8 ms 504 KB correct
16 Correct 9 ms 504 KB correct
17 Correct 7 ms 376 KB correct
18 Correct 4 ms 376 KB correct
19 Correct 7 ms 376 KB correct
20 Correct 7 ms 376 KB correct
21 Correct 7 ms 376 KB correct
22 Correct 6 ms 504 KB correct
23 Correct 6 ms 376 KB correct
24 Correct 6 ms 376 KB correct
25 Correct 2 ms 376 KB correct
26 Correct 6 ms 376 KB correct
27 Correct 6 ms 376 KB correct
28 Correct 4 ms 376 KB correct
29 Correct 3 ms 380 KB correct
30 Correct 6 ms 376 KB correct
31 Correct 5 ms 376 KB correct
32 Correct 6 ms 376 KB correct
33 Correct 5 ms 348 KB correct
34 Incorrect 434 ms 2680 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB correct
2 Correct 2 ms 376 KB correct
3 Incorrect 341 ms 3320 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 256 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 408 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 2 ms 376 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 376 KB correct
10 Correct 2 ms 376 KB correct
11 Correct 2 ms 376 KB correct
12 Correct 2 ms 376 KB correct
13 Correct 2 ms 376 KB correct
14 Correct 9 ms 376 KB correct
15 Correct 8 ms 504 KB correct
16 Correct 9 ms 504 KB correct
17 Correct 7 ms 376 KB correct
18 Correct 4 ms 376 KB correct
19 Correct 7 ms 376 KB correct
20 Correct 7 ms 376 KB correct
21 Correct 7 ms 376 KB correct
22 Correct 6 ms 504 KB correct
23 Correct 6 ms 376 KB correct
24 Correct 6 ms 376 KB correct
25 Correct 2 ms 376 KB correct
26 Correct 6 ms 376 KB correct
27 Correct 6 ms 376 KB correct
28 Correct 4 ms 376 KB correct
29 Correct 3 ms 380 KB correct
30 Correct 6 ms 376 KB correct
31 Correct 5 ms 376 KB correct
32 Correct 6 ms 376 KB correct
33 Correct 5 ms 348 KB correct
34 Incorrect 434 ms 2680 KB WA in grader: NO
35 Halted 0 ms 0 KB -