Submission #1092884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092884		0x34c	Bridges (APIO19_bridges)	C++17	73 / 100	3054 ms	9436 KiB

bridges

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'

using namespace std;

struct change
{
    int a, b, rank_a, rank_b, val_a, val_b;
};

const int MAX_N = 5e4 + 1;
const int MAX_M = 1e5 + 1;

class DSU
{
private:
    stack<change> stk;
    int par[MAX_N], rank[MAX_N], val[MAX_N];

public:
    DSU(int n)
    {
        for (int i = 0; i < n; i++)
        {
            par[i] = i;
            val[i] = 1;
        }
    }

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

    int get_val(int x)
    {
        return val[find(x)];
    }

    bool uni(int a, int b)
    {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;

        if (rank[b] > rank[a])
            swap(a, b);

        stk.push({a, b, rank[a], rank[b], val[a], val[b]});
        par[b] = a;
        if (rank[a] == rank[b])
            rank[a]++;
        val[a] += val[b];
        return true;
    }

    bool back()
    {
        if (stk.empty())
            return false;
        change chg = stk.top();
        stk.pop();

        par[chg.a] = chg.a;
        par[chg.b] = chg.b;
        rank[chg.a] = chg.rank_a;
        rank[chg.b] = chg.rank_b;
        val[chg.a] = chg.val_a;
        val[chg.b] = chg.val_b;
        return true;
    }
};

struct edge
{
    int idx, a, b;
};

struct query
{
    int idx, v, w;
};

edge edges[MAX_M];
int W[MAX_M];
pii edge_ab[MAX_M];
bool mark[MAX_M];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;
    int sqrt_n = sqrt(N);

    for (int i = 0; i < M; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        --a;
        --b;

        edges[i] = {i, a, b};
        edge_ab[i] = {a, b};
        W[i] = w;
    }

    sort(edges, edges + M, [&](edge &a, edge &b)
         { return W[a.idx] > W[b.idx]; });

    int Q;
    cin >> Q;

    vector<int> ans(Q, -1);
    DSU dsu(N);

    vector<int> tmp_w(M, -1);
    for (int q_idx = 0; q_idx < Q; q_idx++)
    {
        vector<query> qrs, qrs2;
        for (int i = 0; i < sqrt_n && q_idx < Q; i++, q_idx++)
        {
            int t, v, w;
            cin >> t >> v >> w;
            --v;

            if (t == 1)
            {
                mark[v] = true;
                qrs.push_back({q_idx, v, w});
            }
            else
                qrs2.push_back({q_idx, v, w});
        }

        sort(qrs2.begin(), qrs2.end(), [&](query &a, query &b)
             { return a.w > b.w; });

        int e_idx = 0;
        for (query &q : qrs2)
        {
            while (e_idx < M && W[edges[e_idx].idx] >= q.w)
            {
                if (mark[edges[e_idx].idx])
                {
                    e_idx++;
                    continue;
                }

                dsu.uni(edges[e_idx].a, edges[e_idx].b);
                e_idx++;
            }

            vector<int> to_add;
            for (query &q2 : qrs)
            {
                if (q2.idx >= q.idx)
                {
                    tmp_w[q2.v] = (tmp_w[q2.v] == -1 ? W[q2.v] : tmp_w[q2.v]);
                    to_add.push_back(q2.v);
                }
                else
                {
                    to_add.push_back(q2.v);
                    tmp_w[q2.v] = q2.w;
                }
            }

            int cnt = 0;
            for (int &e_i : to_add)
            {
                if (tmp_w[e_i] < q.w)
                    continue;
                cnt += dsu.uni(edge_ab[e_i].first, edge_ab[e_i].second);
            }

            ans[q.idx] = dsu.get_val(q.v);
            while (cnt--)
                dsu.back();

            for (query &q2 : qrs)
                tmp_w[q2.v] = -1;
        }

        for (query &q : qrs)
        {
            mark[q.v] = false;
            W[q.v] = q.w;
        }

        while (dsu.back())
        {
        }

        sort(edges, edges + M, [&](edge &a, edge &b)
             { return W[a.idx] > W[b.idx]; });
        q_idx--;
    }

    for (int a : ans)
        if (a != -1)
            cout << a << endl;
}

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27