Submission #187317

#	Time	Username	Problem	Language	Result	Execution time	Memory
187317		Anai	Bridges (APIO19_bridges)	C++14	0 / 100	3089 ms	12152 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(){
        freopen("bridges.in", "r", stdin);
        freopen("bridges.out", "w", stdout);
        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:179:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
              for (int x=0;x<__q.size();x++){
                           ~^~~~~~~~~~~
bridges.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("bridges.in", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("bridges.out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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