Submission #1158616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158616		byunjaewoo	Bridges (APIO19_bridges)	C++20	100 / 100	2727 ms	14472 KiB

bridges

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=100010, sqrtN=500;
int n, m, q, u[N], v[N], w[N], g[N], ans[N];
bool chk[N];
vector<array<int, 3>> vec, vec2;
vector<int> vec3;
array<int, 3> x[N];
vector<pair<int, int>> rol;

void Rollback(int c) {
    while(c--) g[rol.back().first]=rol.back().second, rol.pop_back();
}
int Find(int x) {return (g[x]>=0)?Find(g[x]):x;}
void Union(int u, int v) {
    u=Find(u), v=Find(v);
    if(g[u]<g[v]) swap(u, v);
    rol.push_back({u, g[u]}), rol.push_back({v, g[v]});
    if(u!=v) g[v]+=g[u], g[u]=v;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++) cin>>u[i]>>v[i]>>w[i];
    cin>>q;
    for(int i=1; i<=q; i++) cin>>x[i][0]>>x[i][1]>>x[i][2];
    for(int i=1; i<=q; i+=sqrtN) {
        fill(chk+1, chk+m+1, false), fill(g+1, g+n+1, -1), vec.clear(), vec2.clear(), vec3.clear(), rol.clear();
        for(int j=i; j<=min(i+sqrtN-1, q); j++) {
            if(x[j][0]==1) chk[x[j][1]]=true;
            else vec2.push_back({x[j][2], x[j][1], j});
        }
        for(int j=1; j<=m; j++) {
            if(!chk[j]) vec.push_back({w[j], u[j], v[j]});
            else vec3.push_back(j);
        }
        sort(vec.begin(), vec.end()), sort(vec2.begin(), vec2.end());
        for(int j=(int)vec2.size()-1, k=(int)vec.size()-1; j>=0; j--) {
            while(k>=0 && vec[k][0]>=vec2[j][0]) Union(vec[k][1], vec[k][2]), k--;
            int cnt=0;
            for(int l=vec2[j][2]-1; l>=i; l--) if(x[l][0]==1 && chk[x[l][1]]) {
                chk[x[l][1]]=false;
                if(x[l][2]>=vec2[j][0]) Union(u[x[l][1]], v[x[l][1]]), cnt++;
            }
            for(int l:vec3) if(chk[l] && w[l]>=vec2[j][0]) Union(u[l], v[l]), cnt++;
            ans[vec2[j][2]]=-g[Find(vec2[j][1])];
            Rollback(2*cnt);
            for(int l=vec2[j][2]-1; l>=i; l--) if(x[l][0]==1) chk[x[l][1]]=true;
        }
        for(int j=i; j<=min(i+sqrtN-1, q); j++) if(x[j][0]==1) w[x[j][1]]=x[j][2];
    }
    for(int i=1; i<=q; i++) if(ans[i]) cout<<ans[i]<<"\n";
    return 0;
}

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