oj.uz

Submission #643176

# Submission time Handle Problem Language Result Execution time Memory
643176 2022-09-21T12:10:57 Z FedShat Rigged Roads (NOI19_riggedroads) C++17
58 / 100
 2000 ms 40400 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;

template<class T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

vector<vector<pair<int, int>>> g;
vector<pair<int, int>> par;
vector<int> tin, tout;

void dfs(int v, int p) {
    static int T = 0;
    tin[v] = T++;
    for (auto [u, i] : g[v]) {
        if (u != p) {
            par[u] = {v, i};
            dfs(u, v);
        }
    }
    tout[v] = T;
}

bool is_anc(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#endif
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> e(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        e[i] = {u, v};
    }
    vector<bool> tr(m);
    g.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        int x;
        cin >> x;
        --x;
        tr[x] = 1;
        auto [u, v] = e[x];
        g[u].push_back({v, x});
        g[v].push_back({u, x});
    }
    par.resize(n, {-1, -1});
    tin.resize(n);
    tout.resize(n);
    dfs(0, -1);
    int ind = 1;
    vector<int> ans(m, -1);
    for (int i = 0; i < m; ++i) {
        if (tr[i]) {
            if (ans[i] == -1) {
                ans[i] = ind++;
            }
            continue;
        }
        auto [u, v] = e[i];
        vector<int> cur;
        while (!is_anc(u, v)) {
            if (ans[par[u].second] == -1) {
                cur.push_back(par[u].second);
            }
            u = par[u].first;
        }
        while (!is_anc(v, u)) {
            if (ans[par[v].second] == -1) {
                cur.push_back(par[v].second);
            }
            v = par[v].first;
        }
        sort(cur.begin(), cur.end());
        for (int j : cur) {
            assert(ans[j] == -1);
            ans[j] = ind++;
        }
        assert(ans[i] == -1);
        ans[i] = ind++;
    }
    for (int i : ans) {
        cout << i << " ";
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 11200 KB Output is correct
2 Correct 75 ms 16408 KB Output is correct
3 Correct 80 ms 9880 KB Output is correct
4 Correct 114 ms 30652 KB Output is correct
5 Correct 121 ms 32300 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 32980 KB Output is correct
2 Correct 211 ms 37988 KB Output is correct
3 Correct 54 ms 10760 KB Output is correct
4 Correct 76 ms 16204 KB Output is correct
5 Correct 239 ms 40400 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 23000 KB Output is correct
2 Correct 70 ms 16100 KB Output is correct
3 Correct 267 ms 36028 KB Output is correct
4 Correct 239 ms 33736 KB Output is correct
5 Correct 14 ms 3216 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 55 ms 11200 KB Output is correct
10 Correct 75 ms 16408 KB Output is correct
11 Correct 80 ms 9880 KB Output is correct
12 Correct 114 ms 30652 KB Output is correct
13 Correct 121 ms 32300 KB Output is correct
14 Execution timed out 2062 ms 16960 KB Time limit exceeded
15 Halted 0 ms 0 KB -