Submission #1122207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122207		Aviansh	Rigged Roads (NOI19_riggedroads)	C++17	10 / 100	220 ms	43720 KiB

riggedroads

#include <bits/stdc++.h>

using namespace std;

struct dsu{
    vector<int>root;
    vector<int>siz;
    dsu(int n){
        root=vector<int>(n);
        iota(root.begin(),root.end(),0);
        siz=vector<int>(n,1);
    }
    bool unite(int x, int y){
        x=findRoot(x);
        y=findRoot(y);
        if(x==y)
            return 0;
        if(siz[x]<siz[y])
            swap(x,y);
        siz[x]+=siz[y];
        root[y]=x;
    }
    int findRoot(int x){
        if(x==root[x]){
            return x;
        }
        return root[x]=findRoot(root[x]);
    }
};

void dfs(int st, vector<pair<int,int>>(&g)[], int p, int pare[],int par[], int d[],int dep){
    par[st]=p;
    d[st]=dep;
    for(pair<int,int>ch:g[st]){
        if(ch.first==p)
            continue;
        pare[ch.first]=ch.second;
        dfs(ch.first,g,st,pare,par,d,dep+1);
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    dsu ds(n);
    array<int,2> edges[m];
    for(int i = 0;i<m;i++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        edges[i][0]=a;
        edges[i][1]=b;
    }
    int r[n-1];
    vector<pair<int,int>>g[n];
    for(int &i : r){
        cin >> i;
        i--;
        int a,b;
        a=edges[i][0];
        b=edges[i][1];
        g[a].push_back({b,i});
        g[b].push_back({a,i});
    }
    sort(r,r+n-1);
    int pare[n];
    int par[n];
    int d[n];
    par[0]=-1;
    pare[0]=-1;
    dfs(0,g,-1,pare,par,d,1);
    int w[n];
    int currw = 1;
    bool vis[m];
    fill(vis,vis+m,0);
    int ind = 0;
    for(int i = 0;i<m;i++){
        if(vis[i])
            continue;
        vis[i]=1;
        if(ind<n-1&&i==r[ind]){
            w[i]=currw;
            currw++;
            ind++;
            continue;
        }
        int a = edges[i][0];
        int b = edges[i][1];
        vector<int>es;
        if(d[a]<d[b]){
            swap(a,b);
        }
        while(pare[a]!=-1&&!vis[pare[a]]&&d[a]>d[b]){
            vis[pare[a]]=1;
            es.push_back(pare[a]);
            if(a==edges[pare[a]][0]){
                a=edges[pare[a]][1];
            }
            else{
                a=edges[pare[a]][0];
            }
        }
        while(((pare[a]!=-1&&!vis[pare[a]])||(pare[b]!=-1&&!vis[pare[b]]))){
            if(a==b){
                break;
            }
            if(pare[a]!=-1&&!vis[pare[a]]){
                vis[pare[a]]=1;
                es.push_back(pare[a]);
                if(a==edges[pare[a]][0]){
                    a=edges[pare[a]][1];
                }
                else{
                    a=edges[pare[a]][0];
                }
            }
            if(pare[b]!=-1&&!vis[pare[b]]){
                vis[pare[b]]=1;
                es.push_back(pare[b]);
                if(b==edges[pare[b]][0]){
                    b=edges[pare[b]][1];
                }
                else{
                    b=edges[pare[b]][0];
                }
            }
        }
        sort(es.begin(),es.end());
        for(int i : es){
            assert(i<m&&i>=0);
            w[i]=currw;
            currw++;
        }
        w[i]=currw;
        currw++;
    }
    for(int i =0;i<m;i++){
        cout << w[i] << " ";
    }
    return 0;
}

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