Submission #321965

#	Time	Username	Problem	Language	Result	Execution time	Memory
321965		ryangohca	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	1394 ms	83508 KiB

riggedroads

#include <iostream>
#include <utility>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>
#include <set>
using namespace std;
int parent[300001];
void init(int N){
    iota(parent, parent + 300001, 0);
}
int leader(int x){
    if (parent[x] == x) return x;
    return parent[x] = leader(parent[x]);
}
void merge_set(int a, int b){
    parent[leader(a)] = leader(b);
}
map<pair<int, int>, int> edgesIdx;
pair<int, int> edges[300001];
vector<int> mst[300001];
int p[300001];
int depth[300001];
int ans[300001];
void dfs(int x, int p, int d){
    ::p[x] = p;
    depth[x] = d;
    for (auto i: mst[x]){
        if (i != p) dfs(i, x, d + 1);
    }
}
int main() {
    int n, e; cin >> n >> e;
    init(n);
    for (int i = 1; i <= e; i++){
        int a, b; cin >> a >> b;
        edges[i] = {a, b};
        edgesIdx[{a, b}] = i;
        edgesIdx[{b, a}] = i;
    }
    for (int i = 0; i < n - 1; i++){
        int g; cin >> g;
        mst[edges[g].first].push_back(edges[g].second);
        mst[edges[g].second].push_back(edges[g].first);
        ans[g] = -1;
    }
    dfs(1, -1, 0);
    int curr = 1;
    for (int i = 1; i <= e; i++){
        if (ans[i] > 0) continue;
        if (ans[i] == -1){
            ans[i] = curr;
            curr++;
            int a = edges[i].first, b = edges[i].second;
            if (depth[a] < depth[b]) swap(a, b);
            merge_set(a, b);
        } else {
            set<int> edgesToFill;
            int a = edges[i].first, b = edges[i].second;
            a = leader(a);
            b = leader(b);
            while (leader(a) != leader(b)){
                if (p[leader(b)] == -1 || depth[a] > depth[b]){
                    int pa = p[leader(a)];
                    if (pa == -1) continue;
                    edgesToFill.insert(edgesIdx[{a, pa}]);
                    merge_set(a, pa);
                    a = leader(a);
                } else {
                    int pb = p[leader(b)];
                    if (pb == -1) continue;
                    edgesToFill.insert(edgesIdx[{b, pb}]);
                    merge_set(b, pb);
                    b = leader(b);
                }
            }
            //sort(edgesToFill.begin(), edgesToFill.end());
            for (auto j : edgesToFill){
                ans[j] = curr;
                curr++;
            }
            ans[i] = curr;
            curr++;
        }
    }
    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