oj.uz

Submission #321953

# Submission time Handle Problem Language Result Execution time Memory
321953 2020-11-13T14:28:21 Z ryangohca Rigged Roads (NOI19_riggedroads) C++17
9 / 100
 2000 ms 68204 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;
            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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 8556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 8556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 29156 KB Output is correct
2 Correct 597 ms 44644 KB Output is correct
3 Correct 797 ms 51820 KB Output is correct
4 Correct 770 ms 63952 KB Output is correct
5 Correct 860 ms 67420 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 460 ms 44032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2099 ms 64364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 48920 KB Output is correct
2 Correct 372 ms 34668 KB Output is correct
3 Incorrect 1107 ms 68204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 8556 KB Output isn't correct
2 Halted 0 ms 0 KB -