Submission #487231

#	Time	Username	Problem	Language	Result	Execution time	Memory
487231		niloyroot	Rigged Roads (NOI19_riggedroads)	C++14	58 / 100	2078 ms	61032 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;
    ll ans[e]={0};
    forp(i,0,e-1){
        if(mst[i]){
            if(!ans[i]){
                ans[i]=cnt;
                cnt++;
            }
        } else {
            vi cyc;
            a=edg[i].first; b=edg[i].second;
            if(len[a]<len[b]){swap(a,b);}
            while(len[a]!=len[b]){
                if(!ans[par[a].second]){
                    cyc.pb(par[a].second);
                }
                a=par[a].first;
            }
            while(a!=b){
                if(!ans[par[b].second]){
                    cyc.pb(par[b].second);
                }
                if(!ans[par[a].second]){
                    cyc.pb(par[a].second);
                }
                a=par[a].first;
                b=par[b].first;
            }
            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: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 0 / 32