Submission #906513

#	Time	Username	Problem	Language	Result	Execution time	Memory
906513		imarn	Bridges (APIO19_bridges)	C++14	100 / 100	1818 ms	94592 KiB

bridges

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e5+5,B=1000;
int pr[N],u[N],v[N],w[N],t[N],x[N],y[N],sz[N];
stack<pii>st;
bool vis[100001]{0};
int ans[100001]{0};
int get(int r){
    return pr[r]==r?r:get(pr[r]);
}
void uni(int a,int b){
    a=get(a),b=get(b);
    if(a==b)return;
    if(sz[a]<sz[b])swap(a,b);
    pr[b]=a;sz[a]+=sz[b];
    st.push({a,b});
}
void rollback(int x){
    while(st.size()>x){
        pii u=st.top();st.pop();
        sz[u.f]-=sz[u.s];pr[u.s]=u.s;
    }
}
vector<int>block[1001];
bool cmp1(int a,int b){
    return y[a]>y[b];
}
bool cmp2(int a,int b){
    return w[a]>w[b];
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>u[i]>>v[i]>>w[i];
    int q;cin>>q;
    for(int i=1;i<=q;i++)cin>>t[i]>>x[i]>>y[i];
    for(int l=1;l<=q;l+=B){
        int r=min(q,l+B-1);
        iota(pr,pr+n+1,0);
        memset(vis,0,sizeof vis);
        vector<int>up,un,qr;
        for(int j=1;j<=n;j++)sz[j]=1;
        for(int j=l;j<=r;j++){
            if(t[j]==1)vis[x[j]]=1,up.pb(j);
            else qr.pb(j);
        }
        for(int j=1;j<=m;j++)if(!vis[j])un.pb(j);
        for(int j=l;j<=r;j++){
            if(t[j]==1)w[x[j]]=y[j];
            else {
                block[j-l].clear();
                for(auto it : up)if(w[x[it]]>=y[j])block[j-l].pb(x[it]);
            }
        }
        sort(qr.begin(),qr.end(),cmp1);
        sort(un.begin(),un.end(),cmp2);
        int cur=0;
        for(int j=0;j<qr.size();j++){
            while(cur<un.size()&&w[un[cur]]>=y[qr[j]])uni(u[un[cur]],v[un[cur]]),cur++;
            int prev=st.size();
            for(auto it : block[qr[j]-l])uni(u[it],v[it]);
            ans[qr[j]] = sz[get(x[qr[j]])];
            rollback(prev);
        }
    }
    for(int i=1;i<=q;i++)if(t[i]==2)cout<<ans[i]<<'\n';
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:25:20: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |     while(st.size()>x){
      |           ~~~~~~~~~^~
bridges.cpp: In function 'int main()':
bridges.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int j=0;j<qr.size();j++){
      |                     ~^~~~~~~~~~
bridges.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             while(cur<un.size()&&w[un[cur]]>=y[qr[j]])uni(u[un[cur]],v[un[cur]]),cur++;
      |                   ~~~^~~~~~~~~~

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