Submission #1200213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200213		adiyer	다리 (APIO19_bridges)	C++20	100 / 100	2454 ms	5164 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

typedef int ll;

const int N = 1e5 + 11;
const int K = 500;

ll n, m, q;
ll u[N], v[N], w[N], tp[N], x[N], y[N], c[N], ans[N], sz[N], p[N], was[N];

vector < pair < ll, ll > > reb, ord;
vector < pair < ll&, ll > > rb;
 
void roll_back(){
    (rb.back().first) = (rb.back().second);
    rb.pop_back();
}
   
ll get(ll x){
    if(x == p[x]) return x;
    return get(p[x]);
}

void unite(ll a, ll b, bool fg){
    a = get(a), b = get(b);
    if(a == b) return;
    if(sz[a] > sz[b]) swap(a, b);
    if(fg) rb.push_back({p[a], p[a]});
    if(fg) rb.push_back({sz[b], sz[b]});
    p[a] = b, sz[b] += sz[a];
}

void solve(){
    cin >> n >> m;
    for(ll i = 1; i <= m; i++) cin >> u[i] >> v[i] >> w[i];
    cin >> q;
    for(ll i = 1; i <= q; i++) cin >> tp[i] >> x[i] >> y[i];
    for(ll i = 1; i <= q; i += K){
        ord.clear(), reb.clear();
        for(ll j = 1; j <= n; j++) sz[j] = 1, p[j] = j;
        for(ll j = i; j <= min(i + K - 1, q); j++){ 
            ord.push_back({y[j], j});
            if(tp[j] == 1) was[x[j]] = 1;
        }
        for(ll j = 1; j <= m; j++)
            if(!was[j])
                reb.push_back({w[j], j});
        sort(reb.begin(), reb.end()), sort(ord.begin(), ord.end());
        ll l = reb.size() - 1;
        for(ll j = ord.size() - 1, id; j >= 0; j--){
            id = ord[j].second;
            if(tp[id] == 1) continue;
            while(l >= 0 && y[id] <= reb[l].first) unite(u[reb[l].second], v[reb[l].second], 0), l--;
            for(ll r = i; r < id; r++)
                if(tp[r] == 1)
                    rb.push_back({w[x[r]], w[x[r]]}), w[x[r]] = y[r];
            for(ll r = i; r <= min(i + K - 1, q); r++)
                if(tp[r] == 1 && y[id] <= w[x[r]])
                    unite(u[x[r]], v[x[r]], 1);
            ans[id] = sz[get(x[id])];
            while(!rb.empty()) roll_back();
        }
        for(ll j = i; j <= min(i + K - 1, q); j++){
            if(tp[j] == 2) cout << ans[j] << '\n';
            else w[x[j]] = y[j], was[x[j]] = 0;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while(tt--) 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