Submission #487916

#	Time	Username	Problem	Language	Result	Execution time	Memory
487916		niloyroot	Rigged Roads (NOI19_riggedroads)	C++14	100 / 100	389 ms	61124 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pl = pair<ll,ll>;
#define pb push_back
#define form(m,it) for(auto it=m.begin(); it!=m.end(); it++)
#define forp(i,a,b) for(ll i=a; i<=b; i++)
#define forn(i,a,b) for(ll i=a; i>=b; i--)
#define newl '\n'
const ll mod = 1000000007;

void solve(){
    ll n,e; cin>>n>>e;

    vector<pl> edg;
    ll a,b;
    forp(i,1,e){
        cin>>a>>b;
        edg.pb({a,b});
    }

    vector<pl> adj[n+1];
    bool mst[e+1]={0};
    forp(i,1,n-1){
        ll t;
        cin>>t; t--;
        mst[t]=1;
        a=edg[t].first; b=edg[t].second;
        adj[a].pb({b,t});
        adj[b].pb({a,t});
    }

    ll len[n+1];
    pl par[n+1];
    function<void(ll,ll)> dfs = [&](ll i, ll pa){
        for(auto u:adj[i]){
            if(u.first!=pa){
                len[u.first]=len[i]+1;
                par[u.first].first=i; 
                par[u.first].second=u.second;
                dfs(u.first,i);
            }
        }
    };
    len[1]=0;
    par[1].first=-1; par[1].second=-1;
    dfs(1,-1);

    ll cnt=1;
    pl shortest_dep[n+1];
    ll link[n+1];
    ll sz[n+1];
    forp(i,1,n){
        link[i]=i;
        sz[i]=1;
        shortest_dep[i].first=len[i];
        shortest_dep[i].second=i;
    }
    ll ans[e]={0};
    ll u,v;
    forp(i,0,e-1){
        if(mst[i]){
            if(!ans[i]){
                ans[i]=cnt;
                cnt++;
                u=edg[i].first; v=edg[i].second;
                while(u!=link[u]){u=link[u];}
                while(v!=link[v]){v=link[v];}

                if(u!=v){
                    if(sz[u]<sz[v]){swap(u,v);}
                    sz[u]+=sz[v];
                    link[v]=u;
                    if(shortest_dep[u].first<shortest_dep[v].first){
						shortest_dep[v]=shortest_dep[u]; 
					} else {
						shortest_dep[u]=shortest_dep[v];
					}
                }
            }
        } else {
            vi cyc;

            u=edg[i].first; v=edg[i].second;
            while(u!=link[u]){u=link[u];}
            while(v!=link[v]){v=link[v];}
            u=shortest_dep[u].second;
            v=shortest_dep[v].second;

			
            while(u!=v){
                if(len[u]<len[v]){swap(u,v);}
                cyc.pb(par[u].second);
                b=par[u].first;
                while(u!=link[u]){u=link[u];}
                while(b!=link[b]){b=link[b];}
                if(u!=b){
                    if(sz[u]<sz[b]){
                        sz[b]+=sz[u];
                        link[u]=b;
                    } else {
                        sz[u]+=sz[b];
                        link[b]=u;
                    }
                    if(shortest_dep[u].first<shortest_dep[b].first){
						shortest_dep[b]=shortest_dep[u]; 
					} else {
						shortest_dep[u]=shortest_dep[b];
					}
                }
                u=shortest_dep[u].second;
            }

            sort(cyc.begin(), cyc.end());
            for(auto ed:cyc){

                ans[ed]=cnt;
                cnt++;
            }
            ans[i]=cnt; cnt++;
        }

        cout<<ans[i]<<" ";
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1; //cin>>t;
    while(t--)solve();
}

• 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