Submission #1193126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193126		loom	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	196 ms	57840 KiB

riggedroads

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'

vector<pair<int,int>> g[300001];
int par[300001];
int id[300001];
int d[300001];
int p[300001];
vector<int> ids;

void dfs(int v){
	for(auto [ch, i] : g[v]){
		if(ch == par[v]) continue;

		d[ch] = d[v]+1;
		id[ch] = i;
		par[ch] = v;
		dfs(ch);
	}
}

int find(int x){
	return (x == p[x] ? x : (p[x] = find(p[x])));
}

int unite(int x, int y, int i){
	x = find(x);
	if(x == y) return x;

	ids.push_back(i);
	p[y] = x;
	return x;
}

inline void solve(){
	int n, m;
	cin>>n>>m;
	vector<tuple<int,int,int>> e;
	for(int i=0; i<m; i++){
		int u, v;
		cin>>u>>v;
		e.push_back({u, v, i});
	}

	vector<int> r(m, 0);
	for(int i=0; i<n-1; i++){
		int x;
		cin>>x;
		r[--x] = 1;
	}

	int x;
	for(auto [u, v, i] : e){
		if(r[i]){
			g[u].push_back({v, i});
			g[v].push_back({u, i});
			x = u;
		}
	}

	dfs(x);
	for(int i=1; i<=n; i++) p[i] = i;
	vector<int> ans(m, -1);
	int cnt = 0;

	for(auto [u, v, i] : e){
		if(r[i]){
			if(ans[i] == -1){
				ans[i] = ++cnt;

				if(d[u] < d[v]) swap(u, v);
				unite(par[u], u, 0);
				ids.clear();
			}
			continue;
		}

		u = find(u);
		v = find(v);
		while(u != v){
			if(d[u] < d[v]) swap(u, v);
			u = unite(par[u], u, id[u]);
		}

		sort(ids.begin(), ids.end());
		for(int x : ids) ans[x] = ++cnt;
		ans[i] = ++cnt;
		ids.clear();
	}

	for(int i=0; i<m; i++) cout<<ans[i]<<" ";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);cout.tie(NULL);

	int t = 1;
	//cin>>t;
	while(t--) solve();

	return 0;
}

• 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