Submission #1312207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312207		aryan	Rigged Roads (NOI19_riggedroads)	C++20	49 / 100	2096 ms	36352 KiB

riggedroads

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;


int main(){
        
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,e;
    cin >> n >> e;
    vector<pair<int,int>> ed1;
    for(int i = 0;i < e;i++){
        int u,v;
        cin >> u >> v;
        u --;
        v --;
        ed1.push_back({u,v});
    }
    vector<bool> is(e,false);
    vector<vector<pair<int,int>>> adj(n);
    for(int i = 0;i < n - 1;i++){
        int u,v;
        int ind;
        cin >> ind;
        ind --;
        is[ind] = true;
        u = ed1[ind].first;
        v = ed1[ind].second;
        adj[u].push_back({v,ind});
        adj[v].push_back({u,ind});
    }

    set<int> st;
    for(int i = 1;i <= e;i++){
        st.insert(i);
    }
    vector<int> ans(e,-1);
    for(int i = 0;i < e;i++){
        if(is[i]){
            if(ans[i] == -1){
                ans[i] = *st.begin();
                st.erase(st.begin());
            }
            continue;
        }
        int u = ed1[i].first;
        int v = ed1[i].second;
        vector<int> par(n,-1);
        par[u] = i;
        queue<int> q;
        q.push(u);
        while(!q.empty()){
            int uu = q.front();
            q.pop();
            for(pair<int,int> p : adj[uu]){
                int vv = p.first;
                int ind = p.second;
                if(par[vv] == -1){
                    par[vv] = ind;
                    q.push(vv);
                }
            }
        }
        vector<int> bad;
        int cur = v;
        while(cur != u){
            int cure = par[cur];
            if(ans[cure] == -1){
                bad.push_back(cure);
            }
            if(ed1[cure].first == cur){
                cur = ed1[cure].second;
            }else{
                cur = ed1[cure].first;
            }
        }
        sort(bad.begin(),bad.end());
        for(int &e : bad){
            ans[e] = *st.begin();
            st.erase(st.begin());
        }
        ans[i] = *st.begin();
        st.erase(st.begin());
    } 

    for(int i = 0;i < e;i++){
        cout << ans[i] << " ";
    }
    cout << '\n';

    return 0;
}

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