Submission #715430

#	Time	Username	Problem	Language	Result	Execution time	Memory
715430		SlavicG	Bridges (APIO19_bridges)	C++17	100 / 100	2283 ms	171976 KiB

bridges

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long

#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int N = 1e5 + 5, S = 1000;
int p[N], s[N], a[N], b[N], c[N], type[N], x[N], y[N], w[N], ans[N], used[N]; 
vector<int> consider[N];
stack<pair<int, int>> st;

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

void solve() {
    int n, m; cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        cin >> a[i] >> b[i] >> w[i];
    }
    int q; cin >> q;
    for(int i = 1; i <= q; ++i) {
        cin >> type[i] >> x[i] >> y[i];
    }
    for(int j = 1; j <= q; j += S) {
        int l = j, r = min(j + S - 1, q);
        for(int i = 0; i < N; ++i) {
            p[i] = i, s[i] = 1, used[i] = 0;
        }
        vector<int> active;
        for(int i = l; i <= r; ++i) {
            if(type[i] == 1) {
                used[x[i]] = 1, active.pb(x[i]);
            }
        }
        vector<int> edges;
        for(int i = 1; i <= m; ++i) {
            if(!used[i]) edges.pb(i);
        }
        vector<int> queries;
        for(int i = l; i <= r; ++i) {
            if(type[i] == 1) {
                w[x[i]] = y[i];
            } else {
                queries.pb(i);
                for(int k: active) {
                    if(w[k] >= y[i]) consider[i].pb(k);
                }
            }
        }
        sort(all(edges), [&](int i, int j){return w[i] < w[j];});
        sort(all(queries), [&](int i, int j){return y[i] > y[j];});
        for(int i: queries) {
            while(sz(edges) && w[edges.back()] >= y[i]) {
                uni(a[edges.back()], b[edges.back()]);
                edges.pop_back();
            }
            int remsz = sz(st);
            for(int j: consider[i]) {
                uni(a[j], b[j]);
            }
            ans[i] = s[get(x[i])];

            while(sz(st) > remsz) {
                int a = st.top().first, b = st.top().second;
                p[a] = a, s[b] -= s[a];
                st.pop();
            }
        }
    }
    for(int i = 1; i <= q; ++i) if(type[i] == 2) cout << ans[i] << "\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}

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