Submission #1122173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122173		ihne	Rigged Roads (NOI19_riggedroads)	C++17	36 / 100	317 ms	262144 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
const int mn=3e5+5;
int tin[mn],tout[mn],timer,dom[mn];
int A[mn],B[mn],ans[mn];
bool ch[mn];
vector<int> lca,dw[mn];
int up[mn];
vector<int> g[mn];
int st[20][2*mn],pos[2*mn],h[mn],lg[2*mn],dd[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=u^A[id]^B[id];
		if (v==p) continue;
		dom[id]=u;
		dd[id]=v;
		dw[id].pb(v);
		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){
	if (l>r) swap(l,r);
	int k=lg[r-l];
//	cout<<st[k][l]<<" "<<r-(1<<k)+1<<"\n";
	return min(st[k][l],st[k][r-(1<<k)+1]);
}
signed main(){
//	freopen("a.inp","r",stdin);
//	freopen("a.ans","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);
		g[B[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++;
			for (int x:dw[i]) {
				up[x]=up[dom[i]];
				dw[up[dom[i]]].pb(x);
			}
		}
		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(dom[up[u]],v)){
					edge.pb(up[u]);
					int nd=dom[up[u]];
					for (int x:dw[up[u]]){
						up[x]=up[nd];
						dw[up[nd]].pb(x);
					}
					u=nd;
				}
//				cout<<dep<<"\n";
//				cout<<h[dom[up[u]]]<<"\n";
				if (h[dom[up[u]]]==dep){
					edge.pb(up[u]);
					int nd=dom[up[u]];
					for (int x:dw[up[u]]){
						up[x]=up[nd];
						dw[up[nd]].pb(x);
					}
					u=nd;
				}
			}
			if (!is_ancs(v,u)) {
				while (!is_ancs(dom[up[v]],u)){
					edge.pb(up[v]);
					int nd=dom[up[v]];
					for (int x:dw[up[v]]){
						up[x]=up[nd];
						dw[up[nd]].pb(x);
					}
					v=nd;
				}
//				cout<<up[v]<<"\n";
				if (h[dom[up[v]]]==dep){
					edge.pb(up[v]);
					int nd=dom[up[v]];
					for (int x:dw[up[v]]){
						up[x]=up[nd];
						dw[up[nd]].pb(x);
					}
					v=nd;
				}
			}
			sort(edge.begin(),edge.end());
			for (int id:edge) {
				ans[id]=cur++;
//				del[id]=1;	
			}
			ans[i]=cur++;
		}
	}
	for (int i=1;i<=e;i++) cout<<ans[i]<<" ";
}

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