oj.uz

Submission #647410

# Submission time Handle Problem Language Result Execution time Memory
647410 2022-10-02T12:27:56 Z LeonaRaging Rigged Roads (NOI19_riggedroads) C++14
100 / 100
 351 ms 43444 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "

const ll mod = 1e9 + 7;
const int maxn = 3e5 + 4;
const int INF = 1e9;

struct Edge {
    int u, v;
    int get(int x) {
        return u ^ v ^ x;
    }
};

int n, m, num, par[maxn], h[maxn], nxt[maxn], res[maxn];
bool good[maxn];
vector<Edge> edges;
vector<int> adj[maxn], myVec;


int find(int x) {
    if (x != nxt[x]) nxt[x] = find(nxt[x]);
    return nxt[x];
}

void dfs(int u, int p) {
    nxt[u] = u;
    for (int i : adj[u]) {
        int v = edges[i].get(u);
        if (v != p) {
            par[v] = i;
            h[v] = h[u] + 1;
            dfs(v, u);
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> n >> m;
    edges.pb({0, 0});
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        edges.pb({u, v});
    }
    for (int i = 1; i < n; i++) {
        int idx; cin >> idx;
        good[idx] = 1;
        int u = edges[idx].u, v = edges[idx].v;
        adj[u].pb(idx);
        adj[v].pb(idx);
    }
    dfs(1, 0);
    for (int i = 1; i <= m; i++) {
        int u = edges[i].u, v = edges[i].v;
        u = find(u); v = find(v);
        myVec.clear();
        while (u != v) {
            if (h[u] < h[v])
                swap(u, v);
            myVec.pb(par[u]);
            nxt[u] = edges[par[u]].get(u);
            u = find(u);
        }
        sort(myVec.begin(), myVec.end());
        for (auto idx : myVec) {
            res[idx] = ++num;
        }
        if (!good[i])
            res[i] = ++num;
    }
    for (int i = 1; i <= m; i++)
        cout << res[i] << ' ';
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 4 ms 7476 KB Output is correct
6 Correct 5 ms 7496 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 15276 KB Output is correct
2 Correct 99 ms 19632 KB Output is correct
3 Correct 74 ms 16572 KB Output is correct
4 Correct 131 ms 30192 KB Output is correct
5 Correct 147 ms 31040 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 23936 KB Output is correct
2 Correct 52 ms 15196 KB Output is correct
3 Correct 27 ms 11340 KB Output is correct
4 Correct 62 ms 19712 KB Output is correct
5 Correct 34 ms 12096 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 37396 KB Output is correct
2 Correct 234 ms 43076 KB Output is correct
3 Correct 69 ms 17212 KB Output is correct
4 Correct 82 ms 21708 KB Output is correct
5 Correct 269 ms 43444 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 28480 KB Output is correct
2 Correct 103 ms 21672 KB Output is correct
3 Correct 351 ms 37196 KB Output is correct
4 Correct 283 ms 34536 KB Output is correct
5 Correct 24 ms 9560 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 4 ms 7476 KB Output is correct
6 Correct 5 ms 7496 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 52 ms 15276 KB Output is correct
10 Correct 99 ms 19632 KB Output is correct
11 Correct 74 ms 16572 KB Output is correct
12 Correct 131 ms 30192 KB Output is correct
13 Correct 147 ms 31040 KB Output is correct
14 Correct 79 ms 23936 KB Output is correct
15 Correct 52 ms 15196 KB Output is correct
16 Correct 27 ms 11340 KB Output is correct
17 Correct 62 ms 19712 KB Output is correct
18 Correct 34 ms 12096 KB Output is correct
19 Correct 214 ms 37396 KB Output is correct
20 Correct 234 ms 43076 KB Output is correct
21 Correct 69 ms 17212 KB Output is correct
22 Correct 82 ms 21708 KB Output is correct
23 Correct 269 ms 43444 KB Output is correct
24 Correct 169 ms 28480 KB Output is correct
25 Correct 103 ms 21672 KB Output is correct
26 Correct 351 ms 37196 KB Output is correct
27 Correct 283 ms 34536 KB Output is correct
28 Correct 24 ms 9560 KB Output is correct
29 Correct 303 ms 35384 KB Output is correct
30 Correct 330 ms 35028 KB Output is correct
31 Correct 329 ms 32128 KB Output is correct
32 Correct 79 ms 16704 KB Output is correct
33 Correct 323 ms 32500 KB Output is correct