Submission #936060

#	Time	Username	Problem	Language	Result	Execution time	Memory
936060		abcvuitunggio	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	223 ms	43892 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;
int n,e,a[300001],b[300001],r,mst[300001],p[300001],d[300001],l[300001],id,res[300001];
vector <int> ke[300001],ve;
int f(int i){
    return (l[i]==i?i:l[i]=f(l[i]));
}
void unite(int i, int j){
    l[f(j)]=f(i);
}
void dfs(int u, int par){
    for (int i:ke[u]){
        int v=a[i]^b[i]^u;
        if (v!=par){
            p[v]=i;
            d[v]=d[u]+1;
            dfs(v,u);
        }
    }
}
void walk(int u, int v){
    ve.clear();
    while (true){
        u=f(u);
        v=f(v);
        if (u==v)
            break;
        if (d[u]<d[v])
            swap(u,v);
        int i=p[u];
        unite(a[i]^b[i]^u,u);
        ve.push_back(i);
    }
    sort(ve.begin(),ve.end());
    for (int i:ve)
        res[i]=++id;
}
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> e;
    for (int i=1;i<=e;i++)
        cin >> a[i] >> b[i];
    for (int i=1;i<n;i++){
        cin >> r;
        mst[r]=1;
        ke[a[r]].push_back(r);
        ke[b[r]].push_back(r);
    }
    iota(l,l+n+1,0);
    dfs(1,1);
    for (int i=1;i<=e;i++){
        if (!res[i]){
            walk(a[i],b[i]);
            if (!res[i])
                res[i]=++id;
        }
        cout << res[i] << ' ';
    }
}

• 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