Submission #1305920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305920		StefanSebez	다리 (APIO19_bridges)	C++20	0 / 100	240 ms	6632 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=320;
array<int,3>edges[N],Qs[N];
vector<array<int,3>>grane1;

int par[M],sajz[M];
//vector<pair<int,int>>undo;
void DSU(){for(int i=0;i<M;i++)par[i]=0,sajz[i]=1;}
int FS(int u){if(par[u]==0)return u;return par[u]=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(){DSU();}//{while(!undo.empty())Undo();}
vector<int>E[N];
bool was[N];
int DFS(int u){
    //printf("* %i\n",u);
    int res=sajz[u];
    was[u]=true;
    for(auto i:E[u])if(!was[i])res+=DFS(i);
    return res;
}

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};
        grane1.pb({w,i,-1});
    }
    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};
        if(type==1)grane1.pb({v,u,i});
    }
    sort(grane1.begin(),grane1.end());
    reverse(grane1.begin(),grane1.end());
    bool uzetagrana[n+q+10]={false};
    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]);
        }
        for(int j=0;j<grane1.size();j++){
            auto [w,i,t]=grane1[j];
            if(!skip[i]&&t<l&&!uzetagrana[j])grane.pb(edges[i]),uzetagrana[j]=true;
        }
        //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;
            }
            vector<int>vts;
            for(auto [w,u,v,j]:upd){
                if(edges[j][0]>=qs[i][0]){
                    //undocnt+=US(u,v);
                    int u1=FS(u),v1=FS(v);
                    E[u1].pb(v1);
                    E[v1].pb(u1);
                    vts.pb(u1),vts.pb(v1);
                }
                edges[j][0]=w;
            }
            //for(int i=1;i<=n;i++)printf("%i ",was[i]==1?1:0);printf("\n");
            ans[qs[i][2]]=DFS(FS(qs[i][1]));
            //for(int i=1;i<=n;i++)printf("%i ",sajz[i]);printf("\n");
            //for(int i=1;i<=n;i++)printf("%i ",was[i]==1?1:0);printf("\n");
            //printf("vts: ");for(auto u:vts)printf("%i ",u);printf("\n");
            for(auto u:vts)was[u]=false,E[u].clear();
            was[FS(qs[i][1])]=false;
            //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:46:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     int n,m;scanf("%i%i",&n,&m);
      |             ~~~~~^~~~~~~~~~~~~~
bridges.cpp:48:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         int u,v,w;scanf("%i%i%i",&u,&v,&w);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:52:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     int q;scanf("%i",&q);
      |           ~~~~~^~~~~~~~~
bridges.cpp:54:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         int type,u,v;scanf("%i%i%i",&type,&u,&v);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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