Submission #1158592

#TimeUsernameProblemLanguageResultExecution timeMemory
1158592byunjaewooBridges (APIO19_bridges)C++20
0 / 100
3092 ms14012 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=100010, sqrtN=300;
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];
    fill(g+1, g+n+1, -1);
    for(int i=1; i<=q; i+=sqrtN) {
        fill(chk+1, chk+m+1, false), vec.clear(), vec2.clear(), vec3.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());
        int ccnt=0;
        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--, ccnt++;
            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--) chk[x[l][1]]=true;
        }
        Rollback(2*ccnt);
        for(int j=i; j<=min(i+sqrtN-1, q); j++) if(x[i][0]==1) w[x[i][1]]=x[i][2];
    }
    for(int i=1; i<=q; i++) if(ans[i]) cout<<ans[i]<<"\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...