Submission #456227

#	Time	Username	Problem	Language	Result	Execution time	Memory
456227		astoria	Rigged Roads (NOI19_riggedroads)	C++14	100 / 100	505 ms	67248 KiB

riggedroads

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

#define maxn 300005
int n,e;
int a[maxn],b[maxn];
int r[maxn];
vector<pair<int,int> > adj[maxn];
int depth[maxn];
int p[maxn][20];
int par[maxn];
bool is[maxn];
int ans[maxn];
int pe[maxn];
int ct;
vector<int> bef;
int lc;

int root (int x){
    if (par[x] == -1) return x;
    else return par[x] = root(par[x]);
}

void connect (int u){
    par[u] = root(p[u][0]);
}

void dfs(int x, int pa){
    p[x][0] = pa;
    for (auto i : adj[x]){
        if (i.first == pa) continue;
        depth[i.first] = depth[x] + 1;
        pe[i.first] = i.second;
        dfs(i.first,x);
    }
}

int lca (int a, int b){
    if (depth[a] < depth[b]) swap(a,b);
    for (int k=19; k>=0; k--){
        if (p[a][k] != -1 && depth[p[a][k]] >= depth[b]) a = p[a][k];
    } //now same depth
    if (a==b) return a;
    for (int k=19; k>=0; k--){
        if (p[a][k] != p[b][k]){ a=p[a][k]; b=p[b][k];}
    }
    return p[a][0];
}

void dp (int x){
    if (depth[x] <= depth[lc]) return;
    if (ans[pe[x]] == -1) bef.push_back(x);
	if (root(x) == x) dp(p[x][0]);
	else dp(root(x));
}

int main(){
    ct=1;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    memset(par,-1,sizeof(par));
    memset(is,0,sizeof(is));
    memset(ans,-1,sizeof(ans));
    cin >> n >> e;
    for (int i=1; i<=e; i++) cin >> a[i] >> b[i];
    for (int i=1; i<n; i++){
        cin >> r[i];
        is[r[i]] = 1;
        adj[a[r[i]]].push_back(make_pair(b[r[i]],r[i]));
        adj[b[r[i]]].push_back(make_pair(a[r[i]],r[i]));
    }
    depth[1] = 0;
    dfs(1,-1);
    for (int k=1; k<20; k++){
        for (int i=1; i<=n; i++){
            if (p[i][k-1] != -1){
                p[i][k] = p[p[i][k-1]][k-1];
            } else p[i][k] = -1;
        }
    } //2k decomp

    for (int i=1; i<=e; i++){
        if (ans[i] != -1) continue;
        if (is[i] && ans[i] == -1){ ans[i] = ct; ct++; continue;}
        lc = lca(a[i],b[i]);
        dp(a[i]);
        dp(b[i]);
        vector<int> edg; for (int v : bef) edg.push_back(pe[v]);
        sort(edg.begin(),edg.end());
        for (int v : edg) ans[v] = ct, ct++;
        for (int v : bef){
            par[v] = root(lc);
        }
        ans[i] = ct; ct++;
        bef.clear();
    }
    for (int i=1; i<=e; i++) cout << ans[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