Submission #1271649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271649		StefanSebez	Bridges (APIO19_bridges)	C++20	59 / 100	3095 ms	7176 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
const int N=1e5+50,M=50050,S=360;
array<int,3>edges[N],Qs[N];

int par[M],sajz[M];
vector<pair<int,int>>undo;
void DSU(){for(int i=0;i<M;i++) sajz[i]=1;}
int FS(int u){if(par[u]==0)return u;return FS(par[u]);}
bool US(int u,int v){
    u=FS(u),v=FS(v);
    if(u==v) return 0;
    if(sajz[u]<sajz[v])swap(u,v);
    par[v]=u;
    sajz[u]+=sajz[v];
    undo.pb({u,v});
    return 1;
}
void Undo(){
    auto [u,v]=undo.back();undo.pop_back();
    sajz[u]-=sajz[v];
    par[v]=0;
}
void Clear(){while(!undo.empty())Undo();}

bool skip[N];
int main(){
    DSU();
    int n,m;scanf("%i%i",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v,w;scanf("%i%i%i",&u,&v,&w);
        edges[i]={w,u,v};
    }
    int q;scanf("%i",&q);
    for(int i=0;i<q;i++){
        int type,u,v;scanf("%i%i%i",&type,&u,&v);
        Qs[i]={type,u,v};
    }
    vector<int>res;
    for(int B=0;B*S<q;B++){
        int l=B*S,r=min(q-1,B*S+S-1);
        vector<array<int,4>>upd,qs;
        vector<array<int,3>>grane;
        vector<int>ans;
        int qcnt=0;
        qs.reserve(r-l+1);
        upd.reserve(r-l+1);
        for(int i=l;i<=r;i++){
           auto [type,u,v]=Qs[i];
           if(type==1) skip[u]=true;
           else qs.pb({v,u,qcnt++,i});
        }
        for(int i=1;i<=m;i++){
            if(skip[i]) upd.pb({edges[i][0],edges[i][1],edges[i][2],i});
            else grane.pb(edges[i]);
        }
        sort(grane.begin(),grane.end());
        sort(qs.begin(),qs.end());
        ans.resize(qcnt);
        for(int i=qcnt-1,j=(int)grane.size()-1;i>=0;i--){
            while(j>=0&&grane[j][0]>=qs[i][0]){
                US(grane[j][1],grane[j][2]);
                j--;
            }
            int undocnt=0;
            for(int k=l;k<=qs[i][3];k++){
                auto [type,u,v]=Qs[k];
                if(type==1) edges[u][0]=v;
            }
            for(auto [w,u,v,j]:upd){
                if(edges[j][0]>=qs[i][0]){
                    undocnt+=US(u,v);
                }
                edges[j][0]=w;
            }
            ans[qs[i][2]]=sajz[FS(qs[i][1])];
            while(undocnt--) Undo();
        }
        for(auto i:ans) res.pb(i);
        for(int i=l;i<=r;i++){
            auto [type,u,v]=Qs[i];
            if(type==1) edges[u][0]=v,skip[u]=false;
        }
        Clear();
    }
    for(auto i:res) printf("%i\n",i);
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:36:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     int n,m;scanf("%i%i",&n,&m);
      |             ~~~~~^~~~~~~~~~~~~~
bridges.cpp:38:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         int u,v,w;scanf("%i%i%i",&u,&v,&w);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:41:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     int q;scanf("%i",&q);
      |           ~~~~~^~~~~~~~~
bridges.cpp:43:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         int type,u,v;scanf("%i%i%i",&type,&u,&v);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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