Submission #1335334

#TimeUsernameProblemLanguageResultExecution timeMemory
1335334iamhereforfunBridges (APIO19_bridges)C++20
Compilation error
0 ms0 KiB
// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int LG = 60;
const int INF = 1e9 + 5;
const int K = 301;
const int B = 320;
const int MOD = 1e9 + 7;

struct Dsu
{
    vector<int> parent;
    vector<int> size;
    vector<array<int, 4>> upd;
    Dsu(int n)
    {
        parent.assign(n + 1, 0);
        size.assign(n + 1, 1);
        for (int x = 0; x < n + 1; x++)
        {
            parent[x] = x;
        }
    }
    inline int getParent(int x)
    {
        int i = parent[x];
        if (i == x)
            return x;
        else
            return getParent(parent[x]);
    }
    inline void update(int a, int b, bool c)
    {
        a = getParent(a);
        b = getParent(b);
        if (a != b)
        {
            if (size[a] < size[b])
            {
                swap(a, b);
            }
            if (c)
                upd.push_back({a, b, parent[b], size[b]});
            parent[b] = a;
            size[a] += size[b];
        }
    }
    inline void del()
    {
        while (!upd.empty())
        {
            auto &[a, b, pb, sb] = upd.back();
            parent[b] = pb;
            size[a] -= sb;
            upd.pop_back();
        }
    }
    inline void reset()
    {
        for (int x = 0; x < n + 1; x++)
        {
            parent[x] = x;
            size[x] = 1;
        }
    }
    inline int get(int i)
    {
        return size[getParent(i)];
    }
};

int n, m, q, ans[N], w[N], a[N], b[N];
vector<array<int, 3>> query;
vector<int> add[N];
bool change[N];

inline void solve()
{
    cin >> n >> m;
    for (int x = 0; x < m; x++)
    {
        cin >> a[x] >> b[x] >> w[x];
    }
    cin >> q;
    for (int x = 0; x < q; x++)
    {
        int t, a, b;
        cin >> t >> a >> b;
        if (t == 1)
            a--;
        query.push_back({t, a, b});
    }
    Dsu dsu(n);
    for (int l = 0; l < q; l += B)
    {
        int r = min(l + B - 1, q - 1);
        vector<array<int, 3>> unchange;
        vector<int> update;
        for (int y = l; y <= r; y++)
        {
            // cout << query[y][0] << " " << query[y][1] << " " << query[y][2] << "\n";
            if (query[y][0] == 1)
            {
                change[query[y][1]] = 1;
                update.push_back(query[y][1]);
            }
            else
            {
                unchange.push_back({query[y][2], (y - l) - q, query[y][1]});
            }
        }
        for (int x = 0; x < m; x++)
        {
            if (!change[x])
                unchange.push_back({w[x], a[x], b[x]});
        }
        sort(unchange.rbegin(), unchange.rend());
        for (int y = l; y <= r; y++)
        {
            if (query[y][0] == 1)
            {
                // cout << query[y][1] << " " << query[y][2] << "\n";
                w[query[y][1]] = query[y][2];
            }
            else
            {
                add[y - l].clear();
                for (int i : update)
                {
                    if (w[i] >= query[y][2])
                    {
                        add[y - l].push_back(i);
                    }
                }
            }
        }
        for (auto &[w, i, j] : unchange)
        {
            if (i <= 0)
            {
                for (int k : add[i + q])
                {
                    dsu.update(a[k], b[k], 1);
                }
                ans[i + q + l] = dsu.get(j);
                dsu.del();
            }
            else
            {
                dsu.update(i, j, 0);
            }
        }
        for (int y = l; y <= r; y++)
        {
            if (query[y][0] == 1)
            {
                change[query[y][1]] = 0;
            }
        }
        dsu.reset();
    }
    for (int x = 0; x < q; x++)
    {
        if (query[x][0] == 2)
        {
            cout << ans[x] << "\n";
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In member function 'void Dsu::reset()':
bridges.cpp:71:29: error: 'n' was not declared in this scope
   71 |         for (int x = 0; x < n + 1; x++)
      |                             ^