제출 #1317536

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317536		hoangmc2009	다리 (APIO19_bridges)	C++17	100 / 100	2851 ms	7960 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int maxn=5e4+9,maxm=1e5+9,B=450;
int n,m,q,res[maxm];
array<int,3> E[maxm]; //u,v,w
array<int,3> Q[maxm]; //t,u,w
int dsu[maxn];
stack<pair<int,int>> snapshot;
int find_set(int u) {return dsu[u]<0?u:find_set(dsu[u]);}
void union_set(int u,int v)
{
    u=find_set(u); v=find_set(v);
    if(u!=v)
    {
        if(dsu[u]>dsu[v]) swap(u,v);
        snapshot.push({u,dsu[u]});
        snapshot.push({v,dsu[v]});
        dsu[u]+=dsu[v]; dsu[v]=u;
    }
}
void rollback(int timer)
{
    while(snapshot.size()>timer)
    {
        auto [u,v]=snapshot.top();
        dsu[u]=v; snapshot.pop();
    }
}
int mark[maxm];
vector<array<int,3>> jnL[B];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    fill(dsu+1,dsu+n+1,-1);
    for(int i=1;i<=m;++i) cin>>E[i][0]>>E[i][1]>>E[i][2];
    cin>>q;
    for(int i=0;i<q;++i) cin>>Q[i][0]>>Q[i][1]>>Q[i][2];
    for(int l=0;l<q;l+=B)
    {
        int r=min(q-1,l+B-1);
        rollback(0);
        fill(mark+1,mark+m+1,0);
        vector<int> t10,t2;
        for(int i=l;i<=r;++i)
        {
            jnL[i-l].clear();
            if(Q[i][0]==1) mark[Q[i][1]]=1;
            else t2.push_back(i);
        }
        for(int i=1;i<=m;++i) {if(!mark[i]) t10.push_back(i);}
        sort(t10.begin(),t10.end(),[&](int x,int y){return E[x][2]>E[y][2];});
        sort(t2.begin(),t2.end(),[&](int x,int y){return Q[x][2]>Q[y][2];});
        for(int i=l;i<=r;++i)
        {
            if(Q[i][0]==1) E[Q[i][1]][2]=Q[i][2];
            if(Q[i][0]==2)
            {
                for(int j=l;j<=r;++j)
                    if(Q[j][0]==1) jnL[i-l].push_back(E[Q[j][1]]);
            }
        }
        for(int i=0,j=0;j<t2.size();++j)
        {
            while(i<t10.size() and E[t10[i]][2]>=Q[t2[j]][2])
            {
                union_set(E[t10[i]][0],E[t10[i]][1]);
                ++i;
            }
            int tmp=snapshot.size();
            for(auto& [u,v,w]:jnL[t2[j]-l])
                if(w>=Q[t2[j]][2]) union_set(u,v);
            res[t2[j]]=-dsu[find_set(Q[t2[j]][1])];
            rollback(tmp);
        }
    }
    for(int i=0;i<q;++i) {if(Q[i][0]==2) cout<<res[i]<<'\n';} 
}

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