Submission #494507

#	Time	Username	Problem	Language	Result	Execution time	Memory
494507		blue	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	425 ms	67628 KiB

riggedroads

#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 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32