Submission #187318

#	Time	Username	Problem	Language	Result	Execution time	Memory
187318		Anai	Bridges (APIO19_bridges)	C++14	100 / 100	2395 ms	25452 KiB

bridges

    // bag pula, solutia mea ruleaza in 0.9s la mine pe laptop, muie oj.uz
    #include <cstdio>
        #include <iostream>
        #include <vector>
        #include <utility>
        #include <cstring>
        #include <algorithm>
        using namespace std;
        typedef pair<int,int> ii;
        typedef pair<int,ii> iii;
        typedef pair<ii,ii> iiii;
         
        const int bucket_size=500; ///play with bucket size lmao
         
        struct UFDS{
            int p[50005];
            int r[50005];
            int s[50005];
            
            UFDS(){}
            
            void init(){
                for (int x=0;x<50005;x++){
                    p[x]=x;
                    r[x]=0;
                    s[x]=1;
                }
            }
            
            int parent(int i){return (p[i]==i)?i:p[i]=parent(p[i]);}
            
            void unions(int i,int j){
                i=parent(i),j=parent(j);
                if (i==j) return;
                if (r[i]<r[j]){
                    p[i]=j;
                    s[j]+=s[i];
                }
                else{
                    p[j]=i;
                    s[i]+=s[j];
                    if (r[i]==r[j]) r[i]++;
                }
            }
        };
         
        inline void read(int& x) {
            x = 0;
            char ch = getchar();
            while (ch&16){ //this will break when ‘\n’ or ‘ ‘ is encountered
        		x = (x << 3) + (x << 1) + (ch&15);
        		ch = getchar();
        	}
        }
         
         
        int n,m,q;
        iii edges[100005];
        vector<iiii> unchanged,temp,temp2; ///sorted version of edges
        vector<iii> __q;
        vector<int> changed;
        vector<int> queries;
        iii edges2[100005];
        bool ischanged[100005];
        int ans[1000];
        UFDS *dsu=new UFDS();
         
        ///for dfs
        vector<int> al[500005];
        int visited[500005];
        int dfs_time=0; ///so we know if we visited node before
        int stk[500005]; ///wtf how is this question so cancer
         
        int dfs(int i){
            visited[i]=dfs_time;
            int res=0;
            int node;
            stk[++*stk]=i;
            while (*stk){
                node=stk[*stk];
                --*stk;
                res+=dsu->s[node];
                for (auto &it:al[node]){
                    if (visited[it]!=dfs_time){
                        visited[it]=dfs_time;
                        stk[++*stk]=it;
                    }
                }
            }
            return res;
        }
         
        int main(){
            read(n),read(m);
             
             for (int x=1;x<=m;x++){
                 read(edges[x].second.first),read(edges[x].second.second),read(edges[x].first);
                 unchanged.push_back(iiii(ii(edges[x].second.first,edges[x].second.second),ii(edges[x].first,x)));
             }
             
             sort(unchanged.begin(),unchanged.end(),[](iiii i, iiii j){
                return i.second.first>j.second.first;
             });
             
             read(q);
             int a,b,c;
             int currq;
             int weight;
             vector<iiii>::iterator pnt;
             while (q){
                 __q.clear();
                 memset(ischanged,false,sizeof(ischanged));
                 changed.clear();
                 dsu->init();
                 for (int x=0;x<min(bucket_size,q);x++){
                     read(a),read(b),read(c);
                     __q.push_back(iii(a,ii(b,c)));
                     if (__q.back().first==2) queries.push_back(x);
                     else ischanged[__q.back().second.first]=true;
                 }
                 
                 for (int x=1;x<=m;x++){
                     if (ischanged[x]) changed.push_back(x);
                 }
                 
                 swap(temp,unchanged);
                 for (auto &it:temp){
                     if (!ischanged[it.second.second]) unchanged.push_back(it);
                 }
                 temp.clear();
                 
                 sort(queries.begin(),queries.end(),[](int i,int j){
                     return __q[i].second.second<__q[j].second.second;
                 });
                 /*
                 for (auto &it:unchanged){
                     printf("%d %d %d\n",it->s,it->e,it->w);
                 }
                 printf("\n");
                 //*/
                 pnt=unchanged.begin();
                 while (!queries.empty()){
                     currq=queries.back();
                     weight=__q[currq].second.second;
                     while (pnt!=unchanged.end() && (*pnt).second.first>=weight){
                         dsu->unions((*pnt).first.first,(*pnt).first.second);
                         pnt++;
                     }
                     
                     for (auto &it:changed){
                         edges2[it]=edges[it];
                     }
                     
                     for (int x=0;x<currq;x++){
                         if (__q[x].first==2) continue;
                         edges2[__q[x].second.first].first=__q[x].second.second;
                     }
                     
                     for (auto &it:changed){
                         if (edges2[it].first>=weight){
                             al[dsu->parent(edges2[it].second.first)].push_back(dsu->parent(edges2[it].second.second));
                             al[dsu->parent(edges2[it].second.second)].push_back(dsu->parent(edges2[it].second.first));
                         }
                     }
                     
                     dfs_time++;
                     ans[currq]=dfs(dsu->parent(__q[currq].second.first));
                     
                     for (auto &it:changed){
                         al[dsu->parent(edges2[it].second.first)].clear();
                         al[dsu->parent(edges2[it].second.second)].clear();
                     }
                     queries.pop_back();
                 }
                 
                 
                 for (int x=0;x<__q.size();x++){
                     if (__q[x].first==2) printf("%d\n",ans[x]);
                     else{
                         edges[__q[x].second.first].first=__q[x].second.second;
                     }
                 }
                 for (auto &it:changed){
                     temp.push_back(iiii(ii(edges[it].second.first,edges[it].second.second),ii(edges[it].first,it)));
                 }
                 sort(temp.begin(),temp.end(),[](iiii i, iiii j){
                     return i.second.first>j.second.first; 
                 });
                 
                 swap(temp2,unchanged);
                 pnt=temp.begin();
                 ///merge temp and temp2 into unchanged
                 
                 for (auto &it:temp2){
                     while (pnt!=temp.end() && (*pnt).second.first>it.second.first){
                         unchanged.push_back(*pnt);
                         pnt++;
                     }
                     unchanged.push_back(it);
                 }
                 while (pnt!=temp.end()){
                     unchanged.push_back(*pnt);
                     pnt++;
                 }
                 
                 temp.clear();
                 temp2.clear();
                 q-=min(bucket_size,q);
             }
        }

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:177:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                  for (int x=0;x<__q.size();x++){
                               ~^~~~~~~~~~~

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