Submission #1178765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178765		LeaRouse	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	233 ms	66248 KiB

riggedroads

// \--> alt+92
// ^ alt gr+(costado de la ñ)
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long
#define ff first
#define ss second
#define pip pair<int,pair<int,int>>
const int MAX=3e5+5;
const int MOD=20000837;
using namespace std;
int ST[MAX][20];
vector<pair<int,int>>v[MAX];
int A[MAX];
int B[MAX];
int P[MAX];
bool G[MAX];

int D[MAX];
int R[MAX];
int Pa[MAX];

void sparse_table(int n){
    for(int i=1;i<20;i++){
        for(int j=1;j<=n;j++){
            ST[j][i]=ST[ST[j][i-1]][i-1];
        }
    }
}

int query(int a,int b){
    if(D[a]<D[b]){
        swap(b,a);
    }
    if(D[a]!=D[b]){
        for(int i=19;i>=0;i--){
            if(D[ST[a][i]]>D[b]){
                a=ST[a][i];
            }
        }
        a=ST[a][0];
        if(a==b){
            return a;
        }
    }

    for(int i=19;i>=0;i--){
        if(ST[a][i]!=ST[b][i]){
            a=ST[a][i];
            b=ST[b][i];
        }
    }
    return ST[a][0];
}

int find(int x){
    if(P[x]==x) return x;
    return P[x]=find(P[x]);
}

void uni(int x,int y){
    int a=find(x);
    int b=find(y);
    if(D[a]<D[b]){
        P[b]=a;
    }
    else{
        P[a]=b;
    }
}

void dfs(int x,int p){
    for(auto it:v[x]){
        if(it.ss!=p){
            ST[it.ss][0]=x;
            Pa[it.ss]=it.ff;
            D[it.ss]=1+D[x];
            dfs(it.ss,x);
        }
    }
}

int c=1;
set<int>s;
void subidita(int ini,int final){
    ini=find(ini);
   
    while(D[ini]>D[final]){
        s.insert(Pa[ini]);
        uni(ini,ST[ini][0]);
        ini=find(ST[ini][0]);
    }
}

void go(){
    int n,m;    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>A[i]>>B[i];
    }
    for(int i=1;i<=n;i++){
        P[i]=i;
    }
    for(int i=0;i<n-1;i++){
        int a;  cin>>a;
        G[a]=true;
        v[A[a]].push_back({a,B[a]});
        v[B[a]].push_back({a,A[a]});
    }
    ST[1][0]=1;
    D[1]=1;
    dfs(1,1);
    sparse_table(n);
    for(int i=1;i<=m;i++){
        if(R[i]>0)  continue;
        if(G[i]==false){
            int lca=query(A[i],B[i]);
            subidita(A[i],lca);
            subidita(B[i],lca);
            for(auto it:s){
                R[it]=c;    c++;
            }
            s.clear();
            R[i]=c;
            c++;
        }
        else{
            uni(A[i],B[i]);
            R[i]=c;
            c++;
        }  
    }
   
    for(int i=1;i<=m;i++){
        cout<<R[i]<<" ";
    }
}

int main(){
    fastio;
    go();
    return 0;
}

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