oj.uz

Submission #457865

# Submission time Handle Problem Language Result Execution time Memory
457865 2021-08-07T12:57:53 Z ritul_kr_singh Rigged Roads (NOI19_riggedroads) C++17
17 / 100
 553 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#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);
			}
			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 5 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Runtime error 326 ms 262148 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 20344 KB Output is correct
2 Correct 127 ms 26908 KB Output is correct
3 Correct 105 ms 20632 KB Output is correct
4 Correct 214 ms 43292 KB Output is correct
5 Correct 220 ms 45160 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 222 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 553 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 35156 KB Output is correct
2 Runtime error 443 ms 262148 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Runtime error 326 ms 262148 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -