oj.uz

Submission #487225

# Submission time Handle Problem Language Result Execution time Memory
487225 2021-11-14T20:28:14 Z niloyroot Rigged Roads (NOI19_riggedroads) C++14
9 / 100
 2000 ms 46640 KB 
#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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 14076 KB Output is correct
2 Correct 78 ms 20704 KB Output is correct
3 Correct 78 ms 13732 KB Output is correct
4 Correct 120 ms 42156 KB Output is correct
5 Correct 135 ms 43812 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 24960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 46640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 33196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -