oj.uz

Submission #457871

# Submission time Handle Problem Language Result Execution time Memory
457871 2021-08-07T13:08:16 Z ritul_kr_singh Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 392 ms 41868 KB 
#include <bits/stdc++.h>
using namespace std;
#define sp << ' ' <<
#define nl << '\n'

const int Z = 3e5+1;

int n, e, S[Z], T[Z], h[2][Z], p[Z], d[Z], pEdge[Z], ans[Z];
bool inMST[Z];
vector<array<int, 2>> g[Z];

int find(int u){
	return S[u] < 0 ? u : S[u] = find(S[u]);
}

void unite(int u, int v){
	if(S[u] > S[v]) swap(u, v);
	if(u != v){
		if(d[T[u]] > d[T[v]]) T[u] = T[v];
		S[u] += S[v], S[v] = u;
	}
}

void dfs(int u, int par, int dep, int edge){
	d[u] = dep;
	p[u] = par;
	pEdge[u] = edge;
	for(auto &[v, w] : g[u])
		if(v != par) dfs(v, u, dep+1, w);
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> e;

	for(int i=1; i<=e; ++i){
		cin >> h[0][i] >> h[1][i];
	}
	for(int i=1; i<n; ++i){
		int j; cin >> j;
		inMST[j] = 1;
		g[h[0][j]].push_back({h[1][j], j});
		g[h[1][j]].push_back({h[0][j], j});
	}

	dfs(1, 1, 0, 0);
	fill(S+1, S+n+1, -1);
	iota(T+1, T+n+1, +1);

	int j = 1;

	for(int i=1; i<=e; ++i){
		int u = find(h[0][i]), v = find(h[1][i]);
		if(inMST[i] && !ans[i]){
			ans[i] = j++;
			unite(u, v);	
		}
		if(!ans[i]){
			vector<int> curr;
			while(u != v){
				if(d[T[u]] < d[T[v]]) swap(u, v);

				curr.push_back(pEdge[T[u]]);
				unite(u, find(p[T[u]]));
				u = find(u);
				v = find(v);
			}
			sort(begin(curr), end(curr));
			for(int &w : curr) ans[w] = j++;
			ans[i] = j++;
		}
		cout << ans[i] << ' ';
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 6 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct

Subtask #2
19.0 / 19.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 15072 KB Output is correct
2 Correct 120 ms 18432 KB Output is correct
3 Correct 101 ms 13764 KB Output is correct
4 Correct 192 ms 28620 KB Output is correct
5 Correct 166 ms 29676 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 22780 KB Output is correct
2 Correct 58 ms 14912 KB Output is correct
3 Correct 33 ms 11196 KB Output is correct
4 Correct 71 ms 18796 KB Output is correct
5 Correct 28 ms 11912 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 35668 KB Output is correct
2 Correct 273 ms 40316 KB Output is correct
3 Correct 64 ms 16484 KB Output is correct
4 Correct 92 ms 21216 KB Output is correct
5 Correct 323 ms 41868 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 24340 KB Output is correct
2 Correct 117 ms 21164 KB Output is correct
3 Correct 392 ms 38244 KB Output is correct
4 Correct 320 ms 36036 KB Output is correct
5 Correct 31 ms 9804 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 6 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 6 ms 7500 KB Output is correct
5 Correct 5 ms 7500 KB Output is correct
6 Correct 5 ms 7500 KB Output is correct
7 Correct 5 ms 7372 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 59 ms 15072 KB Output is correct
10 Correct 120 ms 18432 KB Output is correct
11 Correct 101 ms 13764 KB Output is correct
12 Correct 192 ms 28620 KB Output is correct
13 Correct 166 ms 29676 KB Output is correct
14 Correct 96 ms 22780 KB Output is correct
15 Correct 58 ms 14912 KB Output is correct
16 Correct 33 ms 11196 KB Output is correct
17 Correct 71 ms 18796 KB Output is correct
18 Correct 28 ms 11912 KB Output is correct
19 Correct 256 ms 35668 KB Output is correct
20 Correct 273 ms 40316 KB Output is correct
21 Correct 64 ms 16484 KB Output is correct
22 Correct 92 ms 21216 KB Output is correct
23 Correct 323 ms 41868 KB Output is correct
24 Correct 177 ms 24340 KB Output is correct
25 Correct 117 ms 21164 KB Output is correct
26 Correct 392 ms 38244 KB Output is correct
27 Correct 320 ms 36036 KB Output is correct
28 Correct 31 ms 9804 KB Output is correct
29 Correct 343 ms 36364 KB Output is correct
30 Correct 361 ms 36300 KB Output is correct
31 Correct 357 ms 34724 KB Output is correct
32 Correct 105 ms 16680 KB Output is correct
33 Correct 371 ms 35132 KB Output is correct