oj.uz

Submission #917482

# Submission time Handle Problem Language Result Execution time Memory
917482 2024-01-28T10:06:25 Z 406 Rigged Roads (NOI19_riggedroads) C++17
40 / 100
 298 ms 70852 KB 
#include <bits/stdc++.h>
#define int int64_t
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ar = array<int, 2>;

const int64_t INF = 1ll << 60;
const int N = 3e5 + 5;

namespace dsu {
        int dpr[N];
        int gpr(int x) {
                return dpr[x] == x ? x : dpr[x] = gpr(dpr[x]);
        }
        void merge(int u, int v) {
                dpr[gpr(u)] = gpr(v);
        }
}

int st[N], fn[N], T, pr[N], up[N], mn[N], W[N], n, m;
ar E[N];
bool ok[N];
vector<int> ad[N];
vector<ar> adj[N];

bool is_p(int p, int v) {
        return st[p] <= st[v] && fn[v] <= fn[p];
}

void dfs(int v) {
        st[v] = T++;
        for (auto [u, id]: adj[v]) if (u != pr[v]) {
                up[u] = id;
                pr[u] = v;
                dfs(u);
        }
        fn[v] = T;
}

signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr); 
        cin >> n >> m;
        FOR(i, 0, m) {
                cin >> E[i][0] >> E[i][1];
                --E[i][0], --E[i][1];
        }
        FOR(i, 1, n) {
                int x; cin >> x; --x;
                auto [u, v] = E[x];
                adj[v].push_back({u, x});
                adj[u].push_back({v, x});
                ok[x] = true;
        }
        fill(mn, mn + n, n);
        iota(dsu::dpr, dsu::dpr + n, 0);
        
        up[0] = -1;
        dfs(0);
        FOR(i, 0, m) if (!ok[i]) {
               auto [u, v] = E[i];
               int tu = dsu::gpr(u), tv = dsu::gpr(v);
               while (!is_p(tu, v)) {
                       assert(up[tu] != -1);
                       mn[up[tu]] = i;
                       dsu::merge(tu, pr[tu]);
                       tu = dsu::gpr(tu); 
               }
               while (!is_p(tv, u)) {
                       assert(up[tv] != -1);
                        mn[up[tv]] = i;
                        dsu::merge(tv, pr[tv]);
                        tv = dsu::gpr(tv);
               }
        }
        for (int i = m - 1; i >= 0; --i) if (ok[i]) 
                ad[mn[i]].push_back(i);

        int r = m;
        for (int i = m - 1; i >= 0; --i) {
               if (!ok[i]) {
                       W[i] = r--;
                       for (auto t: ad[i]) if (t > i) 
                               W[t] = r--;
               }
               else if (mn[i] > i)
                       W[i] = r--; 
        }
        FOR(i, 0, m) 
                cout << W[i] << ' ';
        cout << '\n';
        return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25176 KB Output is correct
2 Correct 7 ms 25180 KB Output is correct
3 Correct 7 ms 25248 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25176 KB Output is correct
2 Correct 7 ms 25180 KB Output is correct
3 Correct 7 ms 25248 KB Output is correct
4 Incorrect 7 ms 25180 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 46804 KB Output is correct
2 Correct 40 ms 35924 KB Output is correct
3 Correct 23 ms 32596 KB Output is correct
4 Correct 44 ms 40652 KB Output is correct
5 Correct 23 ms 33940 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 61812 KB Output is correct
2 Correct 209 ms 66776 KB Output is correct
3 Correct 46 ms 39292 KB Output is correct
4 Correct 75 ms 43896 KB Output is correct
5 Correct 237 ms 70852 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 52520 KB Output is correct
2 Correct 76 ms 44096 KB Output is correct
3 Correct 298 ms 64448 KB Output is correct
4 Correct 247 ms 62420 KB Output is correct
5 Correct 19 ms 31956 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25176 KB Output is correct
2 Correct 7 ms 25180 KB Output is correct
3 Correct 7 ms 25248 KB Output is correct
4 Incorrect 7 ms 25180 KB Output isn't correct
5 Halted 0 ms 0 KB -