oj.uz

Submission #1076043

# Submission time Handle Problem Language Result Execution time Memory
1076043 2024-08-26T10:43:20 Z NeroZein Simurgh (IOI17_simurgh) C++17
30 / 100
 216 ms 3028 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> find_roads(int n, vector<int> eu, vector<int> ev) {
	
	vector<int> p(n), sz(n);
	
	function<int(int)> get = [&](int v) {
		return p[v] = (p[v] == v ? v : get(p[v]));
	};
	
	auto unite = [&](int u, int v) {
		u = get(u); v = get(v);
		if (u == v) {
			return false;
		}
		if (sz[u] > sz[v]) {
			swap(u, v);
		}
		p[u] = v;
		sz[v] += sz[u];
		return true;
	};
	
	auto init_dsu = [&]() {
		iota(p.begin(), p.end(), 0);
		fill(sz.begin(), sz.end(), 1);
	};
	
	int idd;
	vector<vector<int>> g(n); 
	vector<int> in(n), out(n);
	function<void(int, int)> dfs = [&](int v, int prnt) {
		in[v] = idd++;
		for (int u : g[v]) {
			if (u == prnt) {
				continue;
			}
			dfs(u, v); 
		}
		out[v] = idd - 1;
	};
	auto in_subtree = [&](int prnt, int v) {
		return in[prnt] <= in[v] && out[prnt] >= out[v];
	};
	
	int m = (int) eu.size();
	init_dsu();
	vector<int> in_tree, out_tree;
	for (int i = 0; i < m; ++i) {
		if (unite(eu[i], ev[i])) {
			in_tree.push_back(i);
		} else {
			out_tree.push_back(i);
		}
	}
	
	auto traverse = [&]() {
		for (int i = 0; i < n; ++i) {
			g[i].clear();
		}
		for (int i = 0; i < n - 1; ++i) {
			int label = in_tree[i];
			g[eu[label]].push_back(ev[label]);
			g[ev[label]].push_back(eu[label]);
		}
		idd = 0;
		dfs(0, 0); 
	};
	
	int x = count_common_roads(in_tree);
	vector<int> state(m, -1);
	for (int i : out_tree) {
		vector<int> unknown;
		state[i] = 0;
		traverse();
		assert((int) in_tree.size() == n - 1); 
		for (int j = 0; j < n - 1; ++j) {
			int label = in_tree[j];
			vector<int> tmp = in_tree;
			tmp.erase(tmp.begin() + j);
			tmp.push_back(i);
			int ru = eu[label], rv = ev[label];
			if (in[ru] < in[rv]) {//u is a parent for v
				swap(ru, rv); 
			}
			int cnt = 0; 
			for (int k : {eu[i], ev[i]}) {
				cnt += in_subtree(ru, k);
			}
			
			//~ simulate(tmp); 
			if (cnt != 1) {
				continue; 
			}
			int y = count_common_roads(tmp);
			if (state[label] == -1) {
				if (y > x) {
					state[label] = 0;
					state[i] = 1;
					in_tree = tmp;
					x = y;
					break;
				} else if (y == x) {
					unknown.push_back(label);
				} else {//y < x
					state[label] = 1;
					state[i] = 0;//doesn't matter
					break; 
				}
			} else {
				if (state[label] == 1) {
					continue;
				}
				assert(state[label] == 0);
				if (y > x) {
					x = y; 
					state[i] = 1;
					in_tree = tmp;
				} else {
					assert(y == x);
					state[i] = 0;//doesn't matter
				}
				break;
			}
		}
		for (int j : unknown) {
			state[j] = state[i];
		}
	}
	return in_tree;
}
//~ int common = count_common_roads(r);

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 348 KB correct
4 Correct 0 ms 432 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 1 ms 348 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 1 ms 348 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 4 ms 348 KB correct
15 Correct 3 ms 344 KB correct
16 Correct 3 ms 476 KB correct
17 Correct 3 ms 468 KB correct
18 Correct 1 ms 348 KB correct
19 Correct 2 ms 348 KB correct
20 Correct 2 ms 348 KB correct
21 Correct 2 ms 440 KB correct
22 Correct 3 ms 348 KB correct
23 Correct 3 ms 604 KB correct
24 Correct 3 ms 348 KB correct
25 Correct 1 ms 348 KB correct
26 Correct 3 ms 348 KB correct
27 Correct 3 ms 348 KB correct
28 Correct 1 ms 348 KB correct
29 Correct 1 ms 348 KB correct
30 Correct 4 ms 456 KB correct
31 Correct 4 ms 348 KB correct
32 Correct 4 ms 348 KB correct
33 Correct 3 ms 348 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 348 KB correct
4 Correct 0 ms 432 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 1 ms 348 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 1 ms 348 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 4 ms 348 KB correct
15 Correct 3 ms 344 KB correct
16 Correct 3 ms 476 KB correct
17 Correct 3 ms 468 KB correct
18 Correct 1 ms 348 KB correct
19 Correct 2 ms 348 KB correct
20 Correct 2 ms 348 KB correct
21 Correct 2 ms 440 KB correct
22 Correct 3 ms 348 KB correct
23 Correct 3 ms 604 KB correct
24 Correct 3 ms 348 KB correct
25 Correct 1 ms 348 KB correct
26 Correct 3 ms 348 KB correct
27 Correct 3 ms 348 KB correct
28 Correct 1 ms 348 KB correct
29 Correct 1 ms 348 KB correct
30 Correct 4 ms 456 KB correct
31 Correct 4 ms 348 KB correct
32 Correct 4 ms 348 KB correct
33 Correct 3 ms 348 KB correct
34 Incorrect 216 ms 1116 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB correct
2 Correct 0 ms 348 KB correct
3 Incorrect 175 ms 3028 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 348 KB correct
4 Correct 0 ms 432 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 1 ms 348 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 1 ms 348 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 4 ms 348 KB correct
15 Correct 3 ms 344 KB correct
16 Correct 3 ms 476 KB correct
17 Correct 3 ms 468 KB correct
18 Correct 1 ms 348 KB correct
19 Correct 2 ms 348 KB correct
20 Correct 2 ms 348 KB correct
21 Correct 2 ms 440 KB correct
22 Correct 3 ms 348 KB correct
23 Correct 3 ms 604 KB correct
24 Correct 3 ms 348 KB correct
25 Correct 1 ms 348 KB correct
26 Correct 3 ms 348 KB correct
27 Correct 3 ms 348 KB correct
28 Correct 1 ms 348 KB correct
29 Correct 1 ms 348 KB correct
30 Correct 4 ms 456 KB correct
31 Correct 4 ms 348 KB correct
32 Correct 4 ms 348 KB correct
33 Correct 3 ms 348 KB correct
34 Incorrect 216 ms 1116 KB WA in grader: NO
35 Halted 0 ms 0 KB -