oj.uz

Submission #487231

# Submission time Handle Problem Language Result Execution time Memory
487231 2021-11-14T20:38:59 Z niloyroot Rigged Roads (NOI19_riggedroads) C++14
58 / 100
 2000 ms 61032 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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 440 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12624 KB Output is correct
2 Correct 83 ms 18116 KB Output is correct
3 Correct 76 ms 10840 KB Output is correct
4 Correct 117 ms 38164 KB Output is correct
5 Correct 126 ms 39460 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 45172 KB Output is correct
2 Correct 242 ms 58344 KB Output is correct
3 Correct 51 ms 16812 KB Output is correct
4 Correct 78 ms 24172 KB Output is correct
5 Correct 278 ms 61032 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 32684 KB Output is correct
2 Correct 85 ms 24120 KB Output is correct
3 Correct 285 ms 50596 KB Output is correct
4 Correct 264 ms 46292 KB Output is correct
5 Correct 13 ms 4044 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 440 KB Output is correct
9 Correct 38 ms 12624 KB Output is correct
10 Correct 83 ms 18116 KB Output is correct
11 Correct 76 ms 10840 KB Output is correct
12 Correct 117 ms 38164 KB Output is correct
13 Correct 126 ms 39460 KB Output is correct
14 Execution timed out 2078 ms 23500 KB Time limit exceeded
15 Halted 0 ms 0 KB -