Submission #173650

#TimeUsernameProblemLanguageResultExecution timeMemory
173650errorgornBridges (APIO19_bridges)C++14
100 / 100
2114 ms25444 KiB
#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:176:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
          for (int x=0;x<__q.size();x++){
                       ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...