Submission #708199

#	Time	Username	Problem	Language	Result	Execution time	Memory
708199		dsyz	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	349 ms	55396 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (300005)
ll N,E;
vector<pair<ll,ll> > v[MAXN]; //b, index
pair<ll,ll> edges[MAXN];
ll R[MAXN];
ll parent[MAXN];
ll par[MAXN];
ll depth[MAXN];
ll find_set(ll x){
	if(parent[x] == x) return x;
	parent[x] = find_set(parent[x]);
	return parent[x];
}
bool same_set(ll x,ll y){
	return find_set(x) == find_set(y);
}
void merge_set(ll x,ll y){
	x = find_set(x);
	y = find_set(y);
	if(depth[x] < depth[y]){
		swap(x,y);
	}
	parent[x] = y;
}
void dfs(ll x,ll p){
	for(auto u : v[x]){
		if(u.first != p){
			depth[u.first] = depth[x] + 1;
			par[u.first] = x;
			dfs(u.first,x);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>E;
	for(ll i = 0;i < E;i++){
		cin>>edges[i].first>>edges[i].second;
		edges[i].first--;
		edges[i].second--;	
	}
	ll R[N - 1];
	bool inR[E];
	memset(inR,0,sizeof(inR));
	for(ll i = 0;i < N - 1;i++){
		cin>>R[i];
		R[i]--;
		inR[R[i]] = 1;
		ll a = edges[R[i]].first;
		ll b = edges[R[i]].second;
		v[a].push_back({b,R[i]});
		v[b].push_back({a,R[i]});
	}
	for(ll i = 0;i < N;i++){
		parent[i] = i;
	}
	par[0] = -1;
	dfs(0,-1);
	ll upedgeindex[N]; //edge index between node parent[i] and node i
	memset(upedgeindex,-1,sizeof(upedgeindex));
	for(ll i = 0;i < N;i++){
		for(auto u : v[i]){
			if(depth[u.first] < depth[i]){
				upedgeindex[i] = u.second;
				break;
			}
		}
	}
	ll curweight = 1;
	ll ans[E];
	memset(ans,-1,sizeof(ans));
	for(ll i = 0;i < E;i++){ //list of edges
		if(ans[i] != -1){
			continue;
		}
		if(inR[i]){
			ans[i] = curweight;
			curweight++;
			merge_set(edges[i].first,edges[i].second);
		}else{
			ll a = find_set(edges[i].first);
			ll b = find_set(edges[i].second);
			vector<ll> wait;
			//UFDS jumping on tree (different from binary jumping)
			while(a != b){
				//this will stop when a and b meet at their LCA
				//or above if the above is also merged
				//but as long as they meet, it also works
				if(depth[a] > depth[b]){
					wait.push_back(upedgeindex[a]);
					merge_set(a,par[a]);
					a = find_set(a);
				}else{ 
					//Note that jumping must continue even at same depth as they may not be at same node
					wait.push_back(upedgeindex[b]);
					merge_set(b,par[b]);
					b = find_set(b);
				}
			}
			sort(wait.begin(),wait.end());
			for(auto index : wait){
				ans[index] = curweight;
				curweight++;
			}
			ans[i] = curweight;
			curweight++;
			wait.clear();
		}
	}
	for(ll i = 0;i < E;i++){
		cout<<ans[i]<<" ";
	}
	cout<<'\n';
}

• 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