Submission #676485

#	Time	Username	Problem	Language	Result	Execution time	Memory
676485		penguin133	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	370 ms	48824 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pair<int, int> > 
#define fi first
#define se second
int n,m;
int A[300005], B[300005];
int par[300005];
pi P[300005];
vector<int>tmp;
vector<pi>v[300005];
int dep[300005];
int cnt = 1;

int getr(int x){
	return (par[x] == x ? x : par[x] = getr(par[x]));
}

void merge(int a, int b){
	a = getr(a), b = getr(b);
	if(dep[a] > dep[b])swap(a, b);
	if(a != b)par[b] = a;
}
bool vis[500005];
int mrk[500005];
void solve(){
	cin >> n >> m;
	for(int i=1;i<=m;i++)cin >> A[i] >> B[i];
	
	for(int i=1;i<n;i++){
		int x;cin >> x;
		vis[x] = 1;
		v[A[x]].push_back({B[x], x});
		v[B[x]].push_back({A[x], x});
	}
	queue<pi>q;
	q.push({1, -1});
	while(!q.empty()){
		pi x = q.front(); q.pop();
		if(x.se == -1)dep[x.fi] = 1;
		if(x.se != -1)P[x.fi] = {(A[x.se] == x.fi ? B[x.se] : A[x.se]),x.se};
		for(auto [i, j] : v[x.fi])if(!dep[i])q.push({i, j}), dep[i] = dep[x.fi] + 1;
	}
	//for(int i=1;i<=n;i++)cout << P[i].fi << " " << P[i].se << '\n';
	set<int>s;
	for(int i=1;i<=n;i++)par[i] = i;
	for(int i=1;i<=m;i++){
		if(mrk[i])continue;
		if(vis[i])mrk[i] = cnt++, merge(A[i], B[i]);
		else{
			tmp.clear();
			int a = A[i], b = B[i];
			a = getr(a), b = getr(b);
			while(a != b){
				if(dep[a] > dep[b]){
					tmp.push_back(P[a].se);
					merge(P[a].fi, a);
					a = getr(a);
				}
				else{
					tmp.push_back(P[b].se);
					merge(P[b].fi, b);
					b = getr(b);
				}
			}
			sort(tmp.begin(), tmp.end());
			for(auto j : tmp)if(!mrk[j])mrk[j] = cnt++;
			mrk[i] = cnt++;
		}
	}
	for(int i=1;i<=m;i++)cout << mrk[i] << " ";
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

riggedroads.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main(){
      | ^~~~

• 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