oj.uz

Submission #494507

# Submission time Handle Problem Language Result Execution time Memory
494507 2021-12-15T16:25:31 Z blue Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 425 ms 67628 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int mx = 300'000;
const int lg = 18;

using vi = vector<int>;
using pii = pair<int, int>;

int N, E;
vi A(1+mx), B(1+mx);
vi good(1+mx, 0);
vector<pii> edge[1+mx];


vi depth(1+mx, 1);

int anc[1+mx][1+lg];
vi par_edge(1+mx);

void dfs(int u, int p)
{
    for(pii h: edge[u])
    {
        int v = h.first;
        int e = h.second;

        if(v == p) continue;

        par_edge[v] = e;
        anc[v][0] = u;
        depth[v] = 1 + depth[u];
        dfs(v, u);
    }
}

int lca(int u, int v)
{
    if(depth[u] > depth[v]) swap(u, v);
    for(int e = lg; e >= 0; e--)
    {
        if(depth[v] - (1 << e) < depth[u]) continue;
        v = anc[v][e];
    }
    if(u == v) return u;
    for(int e = lg; e >= 0; e--)
    {
        if(anc[u][e] != anc[v][e])
        {
            u = anc[u][e];
            v = anc[v][e];
        }
    }
    return anc[u][0];
}



struct ds
{
    vi par = vi(1+mx);
    vi st = vi(1+mx, 1);
    vi rt = vi(1+mx);

    ds()
    {
        for(int i = 1; i <= N; i++) par[i] = rt[i] = i;
    }

    int root(int u)
    {
        if(par[u] == u) return u;
        else
        {
            par[u] = root(par[u]);
            return par[u];
        }
    }

    void join(int u, int v)
    {
        u = root(u);
        v = root(v);
        if(u == v) return;
        if(st[u] < st[v]) swap(u, v);
        par[v] = u;
        st[u] += st[v];
        rt[u] = ((depth[rt[u]] < depth[rt[v]]) ? rt[u] : rt[v]);
    }

    bool connected(int u, int v)
    {
        return root(u) == root(v);
    }
};






int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N >> E;
    for(int j = 1; j <= E; j++)
    {
        cin >> A[j] >> B[j];
    }

    for(int i = 1; i <= N-1; i++)
    {
        int g;
        cin >> g;
        good[g] = 1;
        edge[A[g]].push_back({B[g], g});
        edge[B[g]].push_back({A[g], g});
    }
    // cerr << "done\n";

    depth[0] = 0;
    anc[0][0] = 0;
    anc[1][0] = 0;
    dfs(1, 0);
    for(int e = 1; e <= lg; e++)
    {
        for(int u = 0; u <= N; u++)
        {
            anc[u][e] = anc[ anc[u][e-1] ][e-1];
        }
    }
    vi W(1+E, 0);
    int curr_w = 0;

    ds DSU;
    // cerr << "pre done\n";

    for(int e = 1; e <= E; e++)
    {
        // cerr << "e = " << e << '\n';
        if(W[e]) continue;

        if(good[e]) W[e] = ++curr_w;
        else
        {
            vi new_edges;
            int L = lca(A[e], B[e]);
            // cerr << "lca found\n";
            int a = A[e], b = B[e];
            while(DSU.root(a) != DSU.root(L))
            {
                // cerr << a << '\n';
                a = DSU.root(a);
                new_edges.push_back(par_edge[DSU.rt[a]]);
                DSU.join(a, anc[DSU.rt[a]][0]);
            }
            // cerr << "w1 done\n";

            while(DSU.root(b) != DSU.root(L))
            {
                // cerr << ""
                b = DSU.root(b);
                new_edges.push_back(par_edge[DSU.rt[b]]);
                DSU.join(b, anc[DSU.rt[b]][0]);
            }
            // cerr << "w2 done\n";

            sort(new_edges.begin(), new_edges.end());
            for(int q: new_edges)
                if(!W[q])
                    W[q] = ++curr_w;
            W[e] = ++curr_w;
        }
    }

    for(int i = 1; i <= E; i++) cout << W[i] << ' ';
    cout << '\n';
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16716 KB Output is correct
2 Correct 7 ms 16720 KB Output is correct
3 Correct 7 ms 16708 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16716 KB Output is correct
2 Correct 7 ms 16720 KB Output is correct
3 Correct 7 ms 16708 KB Output is correct
4 Correct 8 ms 16848 KB Output is correct
5 Correct 9 ms 16848 KB Output is correct
6 Correct 9 ms 16904 KB Output is correct
7 Correct 8 ms 16720 KB Output is correct
8 Correct 10 ms 16848 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 30216 KB Output is correct
2 Correct 128 ms 35664 KB Output is correct
3 Correct 97 ms 24868 KB Output is correct
4 Correct 162 ms 54544 KB Output is correct
5 Correct 169 ms 56336 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 38136 KB Output is correct
2 Correct 68 ms 25516 KB Output is correct
3 Correct 37 ms 21320 KB Output is correct
4 Correct 77 ms 32504 KB Output is correct
5 Correct 29 ms 23244 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 58256 KB Output is correct
2 Correct 269 ms 64744 KB Output is correct
3 Correct 56 ms 30280 KB Output is correct
4 Correct 107 ms 36928 KB Output is correct
5 Correct 333 ms 67628 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 45732 KB Output is correct
2 Correct 111 ms 36876 KB Output is correct
3 Correct 372 ms 61820 KB Output is correct
4 Correct 336 ms 58660 KB Output is correct
5 Correct 24 ms 20472 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16716 KB Output is correct
2 Correct 7 ms 16720 KB Output is correct
3 Correct 7 ms 16708 KB Output is correct
4 Correct 8 ms 16848 KB Output is correct
5 Correct 9 ms 16848 KB Output is correct
6 Correct 9 ms 16904 KB Output is correct
7 Correct 8 ms 16720 KB Output is correct
8 Correct 10 ms 16848 KB Output is correct
9 Correct 64 ms 30216 KB Output is correct
10 Correct 128 ms 35664 KB Output is correct
11 Correct 97 ms 24868 KB Output is correct
12 Correct 162 ms 54544 KB Output is correct
13 Correct 169 ms 56336 KB Output is correct
14 Correct 109 ms 38136 KB Output is correct
15 Correct 68 ms 25516 KB Output is correct
16 Correct 37 ms 21320 KB Output is correct
17 Correct 77 ms 32504 KB Output is correct
18 Correct 29 ms 23244 KB Output is correct
19 Correct 254 ms 58256 KB Output is correct
20 Correct 269 ms 64744 KB Output is correct
21 Correct 56 ms 30280 KB Output is correct
22 Correct 107 ms 36928 KB Output is correct
23 Correct 333 ms 67628 KB Output is correct
24 Correct 184 ms 45732 KB Output is correct
25 Correct 111 ms 36876 KB Output is correct
26 Correct 372 ms 61820 KB Output is correct
27 Correct 336 ms 58660 KB Output is correct
28 Correct 24 ms 20472 KB Output is correct
29 Correct 401 ms 57084 KB Output is correct
30 Correct 425 ms 58404 KB Output is correct
31 Correct 382 ms 56784 KB Output is correct
32 Correct 128 ms 24996 KB Output is correct
33 Correct 327 ms 57528 KB Output is correct