Submission #698886

#	Time	Username	Problem	Language	Result	Execution time	Memory
698886		finn__	Bridges (APIO19_bridges)	C++17	100 / 100	2724 ms	11316 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("avx2")

struct Edge
{
    unsigned u, v, w;

    bool operator<(Edge const &e) const { return w > e.w; }
};

struct Query
{
    unsigned t, u, w, i;

    bool operator<(Query const &q) const { return w > q.w; }
};

struct DSU
{
    vector<int64_t> p, s;
    stack<int64_t> operations;

    DSU(size_t n) { p = vector<int64_t>(n, -1), s = vector<int64_t>(n, 1); }

    int64_t find(int64_t u)
    {
        while (p[u] >= 0)
            u = p[u];
        return u;
    }

    void unite(int64_t u, int64_t v)
    {
        u = find(u), v = find(v);
        if (u == v)
            return;
        if (s[u] < s[v])
            swap(u, v);
        operations.push(v);
        s[u] += s[v];
        p[v] = u;
    }

    int64_t component_size(int64_t u) { return s[find(u)]; }

    void rollback(size_t n)
    {
        while (n--)
        {
            s[p[operations.top()]] -= s[operations.top()];
            p[operations.top()] = -1;
            operations.pop();
        }
    }
};

Edge e[100000];
Query queries[100000];
unsigned ans[100000];
bool is_changed[100000];

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

    size_t n, m;
    cin >> n >> m;

    for (size_t i = 0; i < m; i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].w;
        e[i].u--, e[i].v--;
    }

    size_t q;
    cin >> q;
    size_t const k = 17 * sqrt(q) / 10;
    for (size_t i = 0; i < q; i++)
    {
        cin >> queries[i].t >> queries[i].u >> queries[i].w;
        queries[i].u--;
        queries[i].i = i;
    }

    for (size_t i = 0; i < q; i += k)
    {
        DSU y(n);
        vector<unsigned> changed;
        vector<Edge> unchanged;
        vector<vector<unsigned>> join(k);
        vector<Query> todo;

        memset(is_changed, 0, 100000);

        for (size_t j = i; j < min(q, i + k); j++)
        {
            if (queries[j].t == 1)
                changed.push_back(queries[j].u), is_changed[queries[j].u] = 1;
            else
                todo.push_back(queries[j]);
        }

        sort(changed.begin(), changed.end());
        changed.resize(unique(changed.begin(), changed.end()) - changed.begin());

        for (size_t j = 0; j < m; j++)
            if (!is_changed[j])
                unchanged.push_back(e[j]);

        for (size_t j = i; j < min(i + k, q); j++)
        {
            if (queries[j].t == 1)
                e[queries[j].u].w = queries[j].w;
            else
            {
                for (unsigned const &h : changed)
                    if (e[h].w >= queries[j].w)
                        join[j - i].push_back(h);
            }
        }

        sort(unchanged.begin(), unchanged.end());
        sort(todo.begin(), todo.end());
        auto it = unchanged.begin();

        for (Query const &x : todo)
        {
            while (it != unchanged.end() && it->w >= x.w)
                y.unite(it->u, it->v), it++;

            size_t s = y.operations.size();
            for (unsigned const &j : join[x.i - i])
                y.unite(e[j].u, e[j].v);

            ans[x.i] = y.component_size(x.u);
            y.rollback(y.operations.size() - s);
        }
    }

    for (unsigned const &x : ans)
        if (x)
            cout << x << '\n';
}

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