Submission #1216761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216761		vanea	Bridges (APIO19_bridges)	C++20	14 / 100	2974 ms	63388 KiB

bridges

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

const int mxN = 1e5+10;
const int B = 350;

int u[mxN], v[mxN], w[mxN], p[mxN], sz[mxN];
int t[mxN], x[mxN], y[mxN], ans[mxN];
bool changed[mxN];
vector<int> to_change[B+1];
stack<int> s;

int get(int x) {
    return p[x] < 0 ? x : p[x] = get(p[x]);
}

void uni(int a, int b) {
    a = get(a); b = get(b);
    if(a == b) return ;
    if(sz[a] > sz[b]) swap(a, b);
    s.push(a);
    sz[b] += sz[a];
    p[a] = b;
}

void rollback(int x) {
    while(s.size() != x) {
        int now = s.top();
        s.pop();
        int par = get(now);
        sz[par] -= sz[now];
        p[now] = -1;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> w[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 += B) {
        int r = min(q ,l+B-1);

        fill(changed, changed+m+1, false);
        fill(p, p+n+1, -1); fill(sz, sz+n+1, 1);

        vector<int> unchanged, upd, ask;
        for(int i = l; i <= r; i++) {
            if(t[i] == 1) {
                changed[x[i]] = true;
                upd.push_back(i);
            }
            else ask.push_back(i);
        }
        for(int i = l; i <= r; i++) {
            if(t[i] == 1) w[x[i]] = y[i];
            else {
                to_change[i-l].clear();
                for(auto it : upd) {
                    if(w[x[it]] >= y[i]) to_change[i-l].push_back(x[it]);
                }
            }
        }
        for(int i = 1; i <= m; i++) {
            if(!changed[i]) unchanged.push_back(i);
        }
        sort(unchanged.begin(), unchanged.end(), [&](int a, int b) {
            return w[a] > w[b];
        });
        sort(ask.begin(), ask.end(), [&](int a, int b) {
            return y[a] > y[b];
        });
        int ptr = 0;
        for(auto i : ask) {
            while(ptr < unchanged.size() && w[unchanged[ptr]] >= y[i]) {
                uni(v[unchanged[ptr]], u[unchanged[ptr]]);
                ++ptr;
            }
            int prev_size = s.size();
            for(auto it : to_change[i-l]) uni(u[it], v[it]);
            ans[i] = sz[get(x[i])];
            rollback(prev_size);
        }
    }
    for(int i = 1; i <= q; i++) {
        if(t[i] == 2) cout << ans[i] << '\n';
    }
    return 0;
}

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