Submission #696548

#	Time	Username	Problem	Language	Result	Execution time	Memory
696548		stevancv	Bridges (APIO19_bridges)	C++14	100 / 100	2507 ms	126620 KiB

bridges

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 5e4 + 2;
const int M = 1e5 + 2;
const int S = 1500;
const int inf = 2e9;
struct Dsu {
    int link[N], sz[N];
    void Init(int n) {
        for (int i = 1; i <= n; i++) {
            link[i] = i;
            sz[i] = 1;
        }
    }
    int Find(int x) {
        if (x == link[x]) return x;
        return Find(link[x]);
    }
    stack<array<int, 4>> s;
    void Unite(int x, int y) {
        x = Find(x); y = Find(y);
        if (sz[x] < sz[y]) swap(x, y);
        s.push({x, y, sz[x], sz[y]});
        if (x == y) return;
        sz[x] += sz[y];
        link[y] = x;
    }
    void RollBack() {
        auto aa = s.top(); s.pop();
        link[aa[0]] = aa[0];
        link[aa[1]] = aa[1];
        sz[aa[0]] = aa[2];
        sz[aa[1]] = aa[3];
    }
}dsu;
int a[M], b[M], c[M], is[M];
int t[M], x[M], y[M], ans[M];
vector<int> qq[S];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    int q; cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> t[i] >> x[i] >> y[i];
    }
    for (int l = 1; l <= q; l += S) {
        int r = min(l + S - 1, q);
        for (int i = l; i <= r; i++) qq[i - l].clear();
        for (int i = 1; i <= m; i++) is[i] = 0;
        vector<int> cx, cy, v;
        for (int i = l; i <= r; i++) {
            if (t[i] == 1) {
                if (is[x[i]] == 0) cx.push_back(x[i]);
                is[x[i]] = 1;
            }
        }
        for (int i = l; i <= r; i++) {
            if (t[i] == 1) c[x[i]] = y[i];
            else {
                for (int j : cx) if (c[j] >= y[i]) qq[i - l].push_back(j);
                v.push_back(i);
            }
        }
        for (int i = 1; i <= m; i++) if (!is[i]) cy.push_back(i);
        sort(cy.begin(), cy.end(), [&] (int i, int j) {
            return c[i] > c[j];
        });
        sort(v.begin(), v.end(), [&] (int i, int j) {
            return y[i] > y[j];
        });
        dsu.Init(n);
        int j = 0;
        for (int i : v) {
            while (j < cy.size() && c[cy[j]] >= y[i]) {
                dsu.Unite(a[cy[j]], b[cy[j]]);
                j += 1;
            }
            for (auto o : qq[i - l]) dsu.Unite(a[o], b[o]);
            ans[i] = dsu.sz[dsu.Find(x[i])];
            for (int j = 0; j < qq[i - l].size(); j++) dsu.RollBack();
        }
    }
    for (int i = 1; i <= q; i++)
        if (t[i] == 2)
            cout << ans[i] << en;
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             while (j < cy.size() && c[cy[j]] >= y[i]) {
      |                    ~~^~~~~~~~~~~
bridges.cpp:92:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             for (int j = 0; j < qq[i - l].size(); j++) dsu.RollBack();
      |                             ~~^~~~~~~~~~~~~~~~~~

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