Submission #1121936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121936		ihne	Rigged Roads (NOI19_riggedroads)	C++17	9 / 100	178 ms	67524 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int mn=3e5+5;
int tin[mn],tout[mn],timer;
int A[mn],B[mn],up[mn],ans[mn];
bool ch[mn];
vector<int> g[mn],lca;
int st[2*mn][20],pos[2*mn],h[mn],lg[2*mn];
void dfs(int u,int p){
	pos[u]=lca.size();
	lca.pb(h[u]);
	tin[u]=++timer;
	for (int id:g[u]){
		int v=B[id];
		if (v==p) continue;
		up[v]=id;
		h[v]=h[u]+1;
		dfs(v,u);
		lca.pb(h[u]);
	}
	tout[u]=timer;
}
bool is_ancs(int u,int v){
	return tin[u]<=tin[v]&&tout[u]>=tout[v];
}
int get(int l,int r){
	int k=lg[r-l];
	return min(st[k][l],st[k][r-(1<<k)+1]);
}
signed main(){
	//freopen("","r",stdin);
	//freopen("","w",stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int i=2;i<=6e5;i++) lg[i]=lg[i>>1]+1;
  int n,e;
  cin>>n>>e;
  for (int i=1;i<=e;i++){
  	int u,v;
  	cin>>u>>v;
  	if (u>v) swap(u,v);
  	A[i]=u;
  	B[i]=v;
	}
	for (int i=1;i<n;i++){
		int id;
		cin>>id;
		ch[id]=1;
		g[A[id]].pb(id);
	}
	lca.pb(0);
	h[1]=1;
	dfs(1,1);
	int N=lca.size()-1;
	for (int i=1;i<=N;i++) st[0][i]=lca[i];
	for (int i=1;i<=19;i++){
		for (int j=1;j+(1<<i)-1<=N;j++){
			st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
		}
	}
	int cur=1;
	tout[0]=timer;
	for (int i=1;i<=e;i++){
		if (ans[i]) continue;
		if (ch[i]) {
			ans[i]=cur++;
			up[B[i]]=up[A[i]];
		}
		else{
			int u=A[i];
			int v=B[i];
			int dep=get(pos[u],pos[v]);
			vector<int> edge;
			if (!is_ancs(u,v)) {
				while (!is_ancs(A[up[u]],v)){
					edge.pb(up[u]);
					int nd=A[up[u]];
					up[u]=up[nd];
					u=nd;
				}
				if (h[A[up[u]]]==dep){
					edge.pb(up[u]);
					int nd=A[up[u]];
					up[u]=up[nd];
					u=nd;
				}
			}
			if (!is_ancs(v,u)) {
				while (!is_ancs(A[up[v]],u)){
					edge.pb(up[v]);
					int nd=A[up[v]];
					up[v]=up[nd];
					v=nd;
				}
				if (h[A[up[v]]]==dep){
					edge.pb(up[v]);
					int nd=A[up[v]];
					up[v]=up[nd];
					v=nd;
				}
			}
			sort(edge.begin(),edge.end());
			for (int id:edge) ans[id]=cur++;
			ans[i]=cur++;
		}
	}
	for (int i=1;i<=e;i++) cout<<ans[i]<<" ";
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 19
• Subtask 3: 9 / 9
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 12
• Subtask 7: 0 / 32