oj.uz

Submission #1075903

# Submission time Handle Problem Language Result Execution time Memory
1075903 2024-08-26T09:41:13 Z NeroZein Simurgh (IOI17_simurgh) C++17
0 / 100
 1 ms 348 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> find_roads(int n, vector<int> eu, vector<int> ev) {
	
	int cc;
	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);
		}
		--cc;
		p[u] = v;
		sz[v] += sz[u];
		return true;
	};
	
	auto init_dsu = [&]() {
		cc = n;
		iota(p.begin(), p.end(), 0);
		fill(sz.begin(), sz.end(), 1);
	};
	
	auto simulate = [&](vector<int> edges) {
		assert((int) edges.size() == n - 1); 
		init_dsu();
		for (int i = 0; i < n - 1; ++i) {
			unite(eu[i], ev[i]);
		}
	};
	
	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);
		}
	}
	
	int x = count_common_roads(in_tree);
	vector<int> state(m, -1);
	for (int i : out_tree) {
		vector<int> unknown;
		state[i] = 0;
		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);
			simulate(tmp); 
			if (cc != 1) {
				continue; 
			}
			int y = count_common_roads(tmp);
			if (state[label] == -1) {
				if (y > x) {
					state[label] = 0;
					state[i] = 1;
					in_tree = tmp;
				} 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;
				}
				//state[label] = 0
				if (y > x) {
					state[i] = 1;
					in_tree = tmp;
				} else {
					assert(y == x);
					state[i] = 0;//doesn't matter
				}
				break;
			}
		}
		for (int label : unknown) {
			state[label] = state[i]; 
		}
	}
	return in_tree;
}
//~ int common = count_common_roads(r);

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB WA in grader: NO
2 Halted 0 ms 0 KB -