Submission #774371

#	Time	Username	Problem	Language	Result	Execution time	Memory
774371		loctildore	Bridges (APIO19_bridges)	C++14	100 / 100	2011 ms	111112 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
// trans rights
#define ll long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
#define BKT 690
int n, m, qrys;
int a[100069], b[100069];
int w[100069];
int t[100069], p[100069], q[100069];
int ans[100069];
vector<int> ext[100069];

int par[100069], sz[100069];
vector<pair<int,int>> lg;
int fnd(int x) {
    return x == par[x] ? x : fnd(par[x]); //don't compress
}
void merge(int x, int y) {
    x = fnd(x); y = fnd(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    lg.push_back({x, y});
    par[y] = x;
    sz[x] += sz[y];
}

void calc(int x) {
    lg.clear();
    for (auto i : ext[x]) {
        merge(a[i], b[i]);
    }
    ans[x] = sz[fnd(p[x])];
    reverse(all(lg));
    for (auto [x, y] : lg) {
        sz[x] -= sz[y];
        par[y] = y;
    }
}

vector<pair<int,int>> vctr;
void solve(int tl, int tr) {
    set<int> spec;
    vctr.clear();
    for (int i = tl; i < tr; i++) if (t[i] == 1) {
        spec.insert(p[i]);
    }
    for (int i = tl; i < tr; i++) {
        if (t[i] == 1) {
            w[p[i]] = q[i];
            continue;
        }
        for (auto t : spec) {
            if (w[t] >= q[i]) {
                ext[i].push_back(t);
            }
        }
        vctr.push_back({q[i], i - 100069});
    }
    for (int i = 0; i < m; i++) {
        if (spec.find(i) == spec.end()) vctr.push_back({w[i], i});
    }
    sort(all(vctr), greater<pair<int,int>>());
    for (int i = 0; i < n; i++) {
        par[i] = i;
        sz[i] = 1;
    }
    for (auto t : vctr) {
        if (t.s >= 0) {
            merge(a[t.s], b[t.s]);
        }
        else {
            calc(t.s + 100069);
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin>>n>>m;
    for (int i = 0; i < m; i++) {
        cin>>a[i]>>b[i]>>w[i];
        a[i]--; b[i]--;
    }
    cin>>qrys;
    for (int i = 0; i < qrys; i++) {
        cin>>t[i]>>p[i]>>q[i];
        p[i]--;
    }
    for (int i = 0; i < qrys; i += BKT) {
        solve(i, min(i + BKT, qrys));
    }
    for (int i = 0; i < qrys; i++) {
        if (t[i] == 2) cout<<ans[i]<<endl;
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void calc(int)':
bridges.cpp:38:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     for (auto [x, y] : lg) {
      |               ^

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