oj.uz

Submission #218288

# Submission time Handle Problem Language Result Execution time Memory
218288 2020-04-01T19:56:29 Z dolphingarlic Rigged Roads (NOI19_riggedroads) C++14
100 / 100
 654 ms 54752 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

pair<int, int> edges[300001];
bool rigged[300001];

int val[300001], tin[300001]{INT_MIN}, tout[300001]{INT_MAX}, timer = 1;
pair<int, int> parent[300001];
vector<pair<int, int>> mst[300001];

inline bool is_ancestor(int a, int b) {
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

void dfs(int node) {
    tin[node] = timer++;
    for (pair<int, int> i : mst[node]) {
        if (!tin[i.first]) {
            parent[i.first] = {node, i.second};
            dfs(i.first);
        }
    }
    tout[node] = timer++;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    FOR(i, 1, m + 1) { cin >> edges[i].first >> edges[i].second; }
    FOR(i, 1, n) {
        int r;
        cin >> r;
        rigged[r] = true;
    }
    FOR(i, 1, m + 1) {
        if (rigged[i]) {
            mst[edges[i].first].push_back({edges[i].second, i});
            mst[edges[i].second].push_back({edges[i].first, i});
        }
    }
    dfs(1);

    int cnt = 1;
    FOR(i, 1, m + 1) {
        // We also have to merge paths together
        int a = edges[i].first, b = edges[i].second;
        set<int> to_process;
        while (!is_ancestor(parent[a].first, b)) {
            to_process.insert(parent[a].second);
            int temp = parent[a].first;
            parent[a] = parent[temp];
            a = temp;
        }
        if (!is_ancestor(a, b)) to_process.insert(parent[a].second);
        while (!is_ancestor(parent[b].first, a)) {
            to_process.insert(parent[b].second);
            int temp = parent[b].first;
            parent[b] = parent[temp];
            b = temp;
        }
        if (!is_ancestor(b, a)) to_process.insert(parent[b].second);

        for (int j : to_process) if (!val[j]) val[j] = cnt++;
        if (!val[i]) val[i] = cnt++;
    }

    FOR(i, 1, m + 1) cout << val[i] << ' ';
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7552 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 10 ms 7424 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7552 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 10 ms 7424 KB Output is correct
4 Correct 11 ms 7552 KB Output is correct
5 Correct 10 ms 7520 KB Output is correct
6 Correct 9 ms 7552 KB Output is correct
7 Correct 9 ms 7424 KB Output is correct
8 Correct 10 ms 7552 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 16108 KB Output is correct
2 Correct 128 ms 20688 KB Output is correct
3 Correct 125 ms 16756 KB Output is correct
4 Correct 216 ms 31692 KB Output is correct
5 Correct 252 ms 32988 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 24820 KB Output is correct
2 Correct 139 ms 15352 KB Output is correct
3 Correct 61 ms 11600 KB Output is correct
4 Correct 223 ms 20856 KB Output is correct
5 Correct 74 ms 12640 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 45964 KB Output is correct
2 Correct 226 ms 51320 KB Output is correct
3 Correct 77 ms 19704 KB Output is correct
4 Correct 101 ms 25976 KB Output is correct
5 Correct 267 ms 54752 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 30072 KB Output is correct
2 Correct 107 ms 21368 KB Output is correct
3 Correct 317 ms 37316 KB Output is correct
4 Correct 301 ms 38520 KB Output is correct
5 Correct 25 ms 9848 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7552 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 10 ms 7424 KB Output is correct
4 Correct 11 ms 7552 KB Output is correct
5 Correct 10 ms 7520 KB Output is correct
6 Correct 9 ms 7552 KB Output is correct
7 Correct 9 ms 7424 KB Output is correct
8 Correct 10 ms 7552 KB Output is correct
9 Correct 84 ms 16108 KB Output is correct
10 Correct 128 ms 20688 KB Output is correct
11 Correct 125 ms 16756 KB Output is correct
12 Correct 216 ms 31692 KB Output is correct
13 Correct 252 ms 32988 KB Output is correct
14 Correct 350 ms 24820 KB Output is correct
15 Correct 139 ms 15352 KB Output is correct
16 Correct 61 ms 11600 KB Output is correct
17 Correct 223 ms 20856 KB Output is correct
18 Correct 74 ms 12640 KB Output is correct
19 Correct 215 ms 45964 KB Output is correct
20 Correct 226 ms 51320 KB Output is correct
21 Correct 77 ms 19704 KB Output is correct
22 Correct 101 ms 25976 KB Output is correct
23 Correct 267 ms 54752 KB Output is correct
24 Correct 187 ms 30072 KB Output is correct
25 Correct 107 ms 21368 KB Output is correct
26 Correct 317 ms 37316 KB Output is correct
27 Correct 301 ms 38520 KB Output is correct
28 Correct 25 ms 9848 KB Output is correct
29 Correct 622 ms 38092 KB Output is correct
30 Correct 654 ms 40220 KB Output is correct
31 Correct 377 ms 35448 KB Output is correct
32 Correct 120 ms 17148 KB Output is correct
33 Correct 383 ms 35832 KB Output is correct