Submission #258355

#	Time	Username	Problem	Language	Result	Execution time	Memory
258355		DS007	Bridges (APIO19_bridges)	C++14	30 / 100	3092 ms	137312 KiB

bridges

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

const int N = 5e4 + 5, M = 1e5, Q = 1e5, BS = 320;

int sz[N], par[N];
stack<int> s;

void reset() {
    iota(par, par + N, 0);
    fill(sz, sz + N, 1);
}

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

void merge(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py)
        return;

    if (sz[px] < sz[py])
        swap(px, py);

    sz[px] += sz[py];
    par[py] = px;
    s.push(py);
}

void rollback(int x) {
    while (s.size() > x) {
        int temp = s.top();
        s.pop();
        sz[par[temp]] -= sz[temp];
        par[temp] = temp;
    }
}

int u[M], v[M], d[M], t[Q], x[Q], y[Q], ans[Q], n, m, q;

int solveTestCase() {
    cin >> n >> m;
    for (int i = 0; i < m; i++)
        cin >> u[i] >> v[i] >> d[i];

    cin >> q;
    for (int i = 0; i < q; i++)
        cin >> t[i] >> x[i] >> y[i];

    for (int i = 0; i < q; i++) {
        if (t[i] == 1)
            x[i]--;
    }

    for (int i = 0; i < q; i += BS) {
        int l = i, r = min(q - 1, i + BS - 1);
        bool changed[m] = {};

        vector<int> unchanged, updates, ask;
        for (int j = l; j <= r; j++) {
            if (t[j] == 1)
                changed[x[j]] = true, updates.push_back(x[j]);
            else
                ask.push_back(j);
        }

        for (int i = 0; i < m; i++) {
            if (!changed[i])
                unchanged.push_back(i);
        }

        vector<int> join[BS];
        for (int j = l; j <= r; j++) {
            if (t[j] == 1) {
                d[x[j]] = y[j];
            } else {
                for (int k : updates) {
                    if (d[k] >= y[j])
                        join[j - l].push_back(k);
                }
            }
        }

        sort(unchanged.begin(), unchanged.end(), [&](auto a, auto b) {
            return d[a] > d[b];
        });

        sort(ask.begin(), ask.end(), [&](auto a, auto b) {
            return y[a] > y[b];
        });

        reset();
        int ptr = 0;
        for (int j : ask) {
            while (ptr != unchanged.size() && d[unchanged[ptr]] >= y[j])
                merge(u[unchanged[ptr]], v[unchanged[ptr]]), ptr++;

            int temp = s.size();
            for (int k : join[j - l])
                merge(u[k], v[k]);

            ans[j] = sz[find(x[j])];
            rollback(temp);
        }
    }

    for (int i = 0; i < q; i++) {
        if (t[i] == 2)
            cout << ans[i] << " \n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--)
        solveTestCase();
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(long long int)':
bridges.cpp:35:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (s.size() > x) {
            ~~~~~~~~~^~~
bridges.cpp: In function 'long long int solveTestCase()':
bridges.cpp:99:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (ptr != unchanged.size() && d[unchanged[ptr]] >= y[j])
                    ~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:115:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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