Submission #1127100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127100		Zero_OP	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	211 ms	45188 KiB

riggedroads

#include <bits/stdc++.h>

using namespace std;

const int MAX = 3e5 + 5;

int N, M, eid[MAX], depth[MAX], par[MAX];
pair<int, int> e[MAX];
vector<int> adj[MAX];
bool in_spanning_tree[MAX];
int ans[MAX];

void dfs(int u){
    for(auto id : adj[u]){
        int v = e[id].first ^ e[id].second ^ u;
        adj[v].erase(find(adj[v].begin(), adj[v].end(), id));
        eid[v] = id;
        depth[v] = depth[u] + 1;
        par[v] = u;
        dfs(v);
    }
}

int info[MAX], up[MAX];

int root(int u){
    return info[u] < 0 ? u : (info[u] = root(info[u]));
}

bool join(int u, int v){
    u = root(u);
    v = root(v);
    if(u == v) return false;
    if(info[u] > info[v]) swap(u, v);
    info[u] += info[v];
    info[v] = u;
    if(depth[up[u]] > depth[up[v]]) up[u] = up[v];
    return true;
}

int get_label(int u){
    return up[root(u)];
}

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

    cin >> N >> M;
    for(int i = 0; i < M; ++i){
        int u, v;
        cin >> u >> v;
        --u, --v;
        e[i] = {u, v};
    }

    for(int i = 0; i < N - 1; ++i){
        int id; cin >> id;
        --id;
        in_spanning_tree[id] = true;
        int u, v;
        tie(u, v) = e[id];
        adj[u].push_back(id);
        adj[v].push_back(id);
    }

    memset(eid, -1, sizeof(eid));
    dfs(0);

    for(int i = 0; i < N; ++i){
        info[i] = -1;
        up[i] = i;
    }

    int cur = 0;
    for(int i = 0; i < M; ++i){
        int u, v; tie(u, v) = e[i];
        if(in_spanning_tree[i]){
            if(ans[i] == 0) {
                ans[i] = ++cur;
                join(u, v);
            }
        } else{
            u = get_label(u);
            v = get_label(v);
            vector<int> ids;

            while(u != v){
                if(depth[u] > depth[v]) swap(u, v);
                ids.push_back(eid[v]);
                join(v, par[v]);
                v = get_label(v);
            }

            sort(ids.begin(), ids.end());
            for(auto x : ids) ans[x] = ++cur;
            ans[i] = ++cur;
        }
    }

    for(int i = 0; i < M; ++i){
        cout << ans[i] << ' ';
    }

    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