Submission #457871

#	Time	Username	Problem	Language	Result	Execution time	Memory
457871		ritul_kr_singh	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	392 ms	41868 KiB

riggedroads

#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 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32