oj.uz

Submission #830085

# Submission time Handle Problem Language Result Execution time Memory
830085 2023-08-18T18:34:16 Z NK_ Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 254 ms 42180 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;
 
#define nl '\n'
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using vi = V<int>;
using ll = long long;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;
using db = long double;

const int INF = 1e9 + 10;

struct DSU {
	vi e; void init(int N) { e = vi(N, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool unite(int x, int y) {
		x = get(x), y = get(y);
		if (x == y) return 0;
		e[x] += e[y]; e[y] = x; return 1;
	}
};


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M; cin >> N >> M;

	vpi E;
	for(int i = 0; i < M; i++) {
		int u, v; cin >> u >> v; --u, --v;
		E.pb(mp(u, v));
	}

	V<vpi> adj(N); vi on(M);
	for(int i = 0; i < N - 1; i++) {
		int x; cin >> x; --x;
		on[x] = 1;
		auto [u, v] = E[x];
		adj[u].pb(mp(v, x));
		adj[v].pb(mp(u, x));
	}

	vi par(N), id(N), dep(N);
	function<void(int)> dfs = [&](int u) {
		for(auto& e : adj[u]) if (e.f != par[u]) {
			id[e.f] = e.s; dep[e.f] = dep[u] + 1; par[e.f] = u; dfs(e.f);
		}
	};

	par[0] = -1, id[0] = -1, dep[0] = 0; dfs(0);


	vi ans(M, -1); int cur = 1; DSU D; D.init(N);
	for(int i = 0; i < M; i++) {
		auto [u, v] = E[i];

		if (on[i]) {
			if (dep[u] > dep[v]) swap(u, v);
			if (D.unite(u, v)) ans[i] = cur++;
			continue;
		}


		vi upd;
		while(1) {
			int a = D.get(u), b = D.get(v);
			if (a == b) break;
			if (dep[a] < dep[b]) swap(a, b);
			assert(par[a] != -1);
			D.unite(par[a], a);
			upd.pb(id[a]);
		}

		sort(begin(upd), end(upd));

		for(auto x : upd) ans[x] = cur++;
		ans[i] = cur++;
	}

	for(auto x : ans) cout << x << " ";
	cout << nl;

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 10184 KB Output is correct
2 Correct 61 ms 17088 KB Output is correct
3 Correct 55 ms 10920 KB Output is correct
4 Correct 96 ms 32488 KB Output is correct
5 Correct 101 ms 33572 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 19444 KB Output is correct
2 Correct 42 ms 9936 KB Output is correct
3 Correct 17 ms 5248 KB Output is correct
4 Correct 49 ms 16280 KB Output is correct
5 Correct 16 ms 6612 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 33832 KB Output is correct
2 Correct 218 ms 40440 KB Output is correct
3 Correct 32 ms 12048 KB Output is correct
4 Correct 58 ms 17440 KB Output is correct
5 Correct 201 ms 42180 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 25424 KB Output is correct
2 Correct 55 ms 19444 KB Output is correct
3 Correct 209 ms 41268 KB Output is correct
4 Correct 196 ms 38060 KB Output is correct
5 Correct 11 ms 3416 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 31 ms 10184 KB Output is correct
10 Correct 61 ms 17088 KB Output is correct
11 Correct 55 ms 10920 KB Output is correct
12 Correct 96 ms 32488 KB Output is correct
13 Correct 101 ms 33572 KB Output is correct
14 Correct 60 ms 19444 KB Output is correct
15 Correct 42 ms 9936 KB Output is correct
16 Correct 17 ms 5248 KB Output is correct
17 Correct 49 ms 16280 KB Output is correct
18 Correct 16 ms 6612 KB Output is correct
19 Correct 146 ms 33832 KB Output is correct
20 Correct 218 ms 40440 KB Output is correct
21 Correct 32 ms 12048 KB Output is correct
22 Correct 58 ms 17440 KB Output is correct
23 Correct 201 ms 42180 KB Output is correct
24 Correct 134 ms 25424 KB Output is correct
25 Correct 55 ms 19444 KB Output is correct
26 Correct 209 ms 41268 KB Output is correct
27 Correct 196 ms 38060 KB Output is correct
28 Correct 11 ms 3416 KB Output is correct
29 Correct 206 ms 38248 KB Output is correct
30 Correct 225 ms 38260 KB Output is correct
31 Correct 254 ms 35008 KB Output is correct
32 Correct 54 ms 11168 KB Output is correct
33 Correct 214 ms 35588 KB Output is correct