oj.uz

Submission #914808

# Submission time Handle Problem Language Result Execution time Memory
914808 2024-01-22T17:26:32 Z f0rizen Rigged Roads (NOI19_riggedroads) C++17
58 / 100
 2000 ms 40512 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

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

struct Edge {
    int to, ind;
};

vector<vector<Edge>> g;
vector<int> par, up;
vector<int> tin, tout;
int timer;

void dfs(int v, int p = -1) {
    tin[v] = timer++;
    for (auto [u, i] : g[v]) {
        if (u != p) {
            par[u] = v;
            up[u] = i;
            dfs(u, v);
        }
    }
    tout[v] = timer++;
}

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

int32_t main() {
#ifdef LOCAL
    freopen("/tmp/input.txt", "r", stdin);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> edg(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        edg[i] = {u, v};
    }
    g.resize(n);
    vector<bool> mst(m);
    for (int i = 1; i < n; ++i) {
        int e;
        cin >> e;
        --e;
        auto [u, v] = edg[e];
        g[u].push_back({v, e});
        g[v].push_back({u, e});
        mst[e] = 1;
    }
    par.resize(n);
    up.resize(n);
    tin.resize(n);
    tout.resize(n);
    dfs(0);
    int cl = 0;
    vector<int> ans(m, -1);
    for (int i = 0; i < m; ++i) {
        if (ans[i] != -1) {
            continue;
        }
        auto [u, v] = edg[i];
        if (mst[i]) {
            ans[i] = cl++;
            continue;
        }
        vector<int> cur;
        while (!is_anc(u, v)) {
            if (ans[up[u]] == -1) {
                cur.push_back(up[u]);
            }
            u = par[u];
        }
        while (!is_anc(v, u)) {
            if (ans[up[v]] == -1) {
                cur.push_back(up[v]);
            }
            v = par[v];
        }
        sort(cur.begin(), cur.end());
        for (auto j : cur) {
            ans[j] = cl++;
        }
        ans[i] = cl++;
    }
    for (auto i : ans) {
        cout << i + 1 << " ";
    }
    cout << "\n";
    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
19.0 / 19.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 11232 KB Output is correct
2 Correct 60 ms 16284 KB Output is correct
3 Correct 58 ms 9936 KB Output is correct
4 Correct 85 ms 30908 KB Output is correct
5 Correct 100 ms 33316 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 33176 KB Output is correct
2 Correct 163 ms 38052 KB Output is correct
3 Correct 30 ms 10992 KB Output is correct
4 Correct 70 ms 16328 KB Output is correct
5 Correct 235 ms 40512 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 23084 KB Output is correct
2 Correct 51 ms 16140 KB Output is correct
3 Correct 201 ms 36092 KB Output is correct
4 Correct 195 ms 33540 KB Output is correct
5 Correct 13 ms 3420 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 32 ms 11232 KB Output is correct
10 Correct 60 ms 16284 KB Output is correct
11 Correct 58 ms 9936 KB Output is correct
12 Correct 85 ms 30908 KB Output is correct
13 Correct 100 ms 33316 KB Output is correct
14 Execution timed out 2031 ms 17116 KB Time limit exceeded
15 Halted 0 ms 0 KB -