Submission #550178

#	Time	Username	Problem	Language	Result	Execution time	Memory
550178		zaneyu	Bridges (APIO19_bridges)	C++14	100 / 100	2433 ms	137112 KiB

bridges

/*input
7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
12
2 1 6
1 1 1
2 1 2
1 2 3
2 2 2
1 5 2
1 3 1
2 2 4
2 4 2
1 8 1
2 1 1
2 1 3
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long,null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll maxn=1e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
int MOD=998244353;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f+1<<' '<<P.s+1;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?" ":"\n");
    return out;
}
ll mult(ll a,ll b){
    return a*b%MOD;
}
ll mult(ll a,ll b,ll mod){
    ll res=0;
    while(b){
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return res;
}
ll mypow(ll a,ll b,ll mod){
    if(b<=0) return 1;
    a%=mod;
    ll res=1LL;
    while(b){
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
 
ll mypow(ll a,ll b){
    a%=MOD;
    if(a==0) return 0;
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
vector<pair<int,pii>> ed;
pair<pii,int> qq[maxn];
const int blk=800;
int par[maxn],rank1[maxn];
int cm=0;
vector<pii> rb;
inline void init(int n){
    REP1(i,n) par[i]=i,rank1[i]=1;
    cm=n;
}
inline int find(int u){
    if(par[u]==u) return u;
    return find(par[u]);
}
inline void merge(int a,int b){
    a=find(a),b=find(b);
    if(a==b){
        rb.pb({a,a});
        return;
    }
    if(rank1[a]>rank1[b]) swap(a,b);
    --cm;
    par[a]=b;
    rank1[b]+=rank1[a];
    rb.pb({a,b});
}
inline void roll(){
    pii z=rb.back();
    int a=z.f,b=z.s;
    rb.pop_back();
    if(a==b) return;
    ++cm;
    par[a]=a;
    rank1[b]-=rank1[a];
}
bool in[maxn];
int ans[maxn];
bool vis[maxn];
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m;
    cin>>n>>m;
    REP(i,m){
        int a,b,c;
        cin>>a>>b>>c;
        c=-c;
        ed.pb({c,{a,b}});
    }
    int q;
    cin>>q;
    REP(i,q) ans[i]=-1;
    REP(i,q/blk+1){
        int sz=min(blk,q-i*blk);
        vector<pair<pii,int>> qr;
        vector<pair<int,pii>> ed1;
        REP(j,sz){
            int x,y,z;
            cin>>x>>y>>z;
            z=-z;
            if(x==1) --y,in[y]=1,ed1.pb({i*blk+j,{y,z}});
            else qr.pb({{z,y},i*blk+j});
            qq[j]={{x,y},z};
        }
        reverse(ALL(ed1));
        vector<pair<int,pii>> ed2;
        REP(i,m){
            if(!in[i]) ed2.pb(ed[i]);
            else ed1.pb({-1,{i,ed[i].f}});
        }
        sort(ALL(ed2));
        sort(ALL(qr));
        init(n);   
        int p=0;
        for(auto x:qr){
            while(p<sz(ed2) and ed2[p].f<=x.f.f){
                merge(ed2[p].s.f,ed2[p].s.s);
                ++p;
            }
			int cnt=0;
            for(auto z:ed1){
                if(z.f<=x.s and z.s.s<=x.f.f and !vis[z.s.f]) merge(ed[z.s.f].s.f,ed[z.s.f].s.s),++cnt;
                if(z.f<=x.s) vis[z.s.f]=1;
            }
            for(auto z:ed1) vis[z.s.f]=0;
            ans[x.s]=rank1[find(x.f.s)];
           	REP(j,cnt) roll();
        }
        REP(j,sz){
            if(qq[j].f.f==1){
                ed[qq[j].f.s].f=qq[j].s;
				in[qq[j].f.s]=0;
            }
        }
    }
    REP(i,q) if(ans[i]!=-1) cout<<ans[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