oj.uz

Submission #321965

# Submission time Handle Problem Language Result Execution time Memory
321965 2020-11-13T14:56:28 Z ryangohca Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 1394 ms 83508 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8556 KB Output is correct
2 Correct 6 ms 8556 KB Output is correct
3 Correct 6 ms 8684 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8556 KB Output is correct
2 Correct 6 ms 8556 KB Output is correct
3 Correct 6 ms 8684 KB Output is correct
4 Correct 7 ms 8812 KB Output is correct
5 Correct 7 ms 8812 KB Output is correct
6 Correct 8 ms 8812 KB Output is correct
7 Correct 7 ms 8684 KB Output is correct
8 Correct 8 ms 8684 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 27748 KB Output is correct
2 Correct 594 ms 41828 KB Output is correct
3 Correct 792 ms 48896 KB Output is correct
4 Correct 744 ms 59868 KB Output is correct
5 Correct 831 ms 62940 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 41708 KB Output is correct
2 Correct 333 ms 32236 KB Output is correct
3 Correct 147 ms 20716 KB Output is correct
4 Correct 319 ms 35052 KB Output is correct
5 Correct 93 ms 18028 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 65900 KB Output is correct
2 Correct 676 ms 79980 KB Output is correct
3 Correct 165 ms 28652 KB Output is correct
4 Correct 235 ms 35980 KB Output is correct
5 Correct 763 ms 83508 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 661 ms 45932 KB Output is correct
2 Correct 357 ms 32876 KB Output is correct
3 Correct 1069 ms 63084 KB Output is correct
4 Correct 997 ms 64108 KB Output is correct
5 Correct 59 ms 13932 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8556 KB Output is correct
2 Correct 6 ms 8556 KB Output is correct
3 Correct 6 ms 8684 KB Output is correct
4 Correct 7 ms 8812 KB Output is correct
5 Correct 7 ms 8812 KB Output is correct
6 Correct 8 ms 8812 KB Output is correct
7 Correct 7 ms 8684 KB Output is correct
8 Correct 8 ms 8684 KB Output is correct
9 Correct 261 ms 27748 KB Output is correct
10 Correct 594 ms 41828 KB Output is correct
11 Correct 792 ms 48896 KB Output is correct
12 Correct 744 ms 59868 KB Output is correct
13 Correct 831 ms 62940 KB Output is correct
14 Correct 460 ms 41708 KB Output is correct
15 Correct 333 ms 32236 KB Output is correct
16 Correct 147 ms 20716 KB Output is correct
17 Correct 319 ms 35052 KB Output is correct
18 Correct 93 ms 18028 KB Output is correct
19 Correct 600 ms 65900 KB Output is correct
20 Correct 676 ms 79980 KB Output is correct
21 Correct 165 ms 28652 KB Output is correct
22 Correct 235 ms 35980 KB Output is correct
23 Correct 763 ms 83508 KB Output is correct
24 Correct 661 ms 45932 KB Output is correct
25 Correct 357 ms 32876 KB Output is correct
26 Correct 1069 ms 63084 KB Output is correct
27 Correct 997 ms 64108 KB Output is correct
28 Correct 59 ms 13932 KB Output is correct
29 Correct 1394 ms 72556 KB Output is correct
30 Correct 1390 ms 73964 KB Output is correct
31 Correct 1205 ms 68152 KB Output is correct
32 Correct 744 ms 49792 KB Output is correct
33 Correct 1200 ms 67004 KB Output is correct