Submission #755173

#	Time	Username	Problem	Language	Result	Execution time	Memory
755173		Ahmed57	Bridges (APIO19_bridges)	C++17	100 / 100	2693 ms	153304 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
int t[100001],x[100001],z[100001];
int u[100001],v[100001],cost[100001];
bool comp1(int a,int b){
    return z[a]>z[b];
}
bool comp2(int a,int b){
    return cost[a]>cost[b];
}
int pr[50001];
int gs[50001];

int findleader(int x){
    if(pr[x]==x){
        return x;
    }
    return findleader(pr[x]);
}
bool samegroup(int x,int y){
    int led1 = findleader(x);
    int led2 = findleader(y);
    return led1==led2;
}
stack<int> st;
void mergegroup(int x,int y){
    int led1 = findleader(x);
    int led2 = findleader(y);
    if(led1==led2)return;
    if(gs[led1]>gs[led2]){
        pr[led2]=led1;
        gs[led1]+=gs[led2];
        st.push(led2);
    }else{
        pr[led1]=led2;
        gs[led2]+=gs[led1];
        st.push(led1);
    }
}
void rollback(int sx){
    while(sx--){
        gs[findleader(st.top())]-=gs[st.top()];
        pr[st.top()] = st.top();
        st.pop();
    }
}
int get(int x){
    int led = findleader(x);
    return gs[led];
}
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i = 1;i<=m;i++){
        cin>>u[i]>>v[i]>>cost[i];
    }
    int q;cin>>q;
    int ans[q+1];
    memset(ans,-1,sizeof ans);
    vector<int> join[q+1];
    for(int i =1;i<=q;i++){
        cin>>t[i]>>x[i]>>z[i];
    }
    for(int l = 1;l<=q;l+=1000){
        for(int i = 1;i<=n;i++){
            pr[i] = i , gs[i] = 1;
        }
        int r = min(q+1,l+1000);
        bool change[m+1] = {0};
        vector<int> ques,upd;
        for(int i = l;i<r;i++){
            if(t[i]==1){
                change[x[i]] = 1;
                upd.push_back(x[i]);
            }else ques.push_back(i);
        }
        sort(ques.begin(),ques.end(),comp1);
        vector<int> unchanged;
        for(int i = 1;i<=m;i++){
            if(!change[i])unchanged.push_back(i);
        }
        sort(unchanged.begin(),unchanged.end(),comp2);
        for(int i = l;i<r;i++){
            if(t[i]==1){
                cost[x[i]] = z[i];
            }else{
                join[i].clear();
                for(auto j:upd){
                    if(cost[j]>=z[i]){
                        join[i].push_back(j);
                    }
                }
            }
        }
        int ptr = 0;
        for(auto i:ques){
            while(ptr<unchanged.size()&&cost[unchanged[ptr]]>=z[i]){
                mergegroup(u[unchanged[ptr]],v[unchanged[ptr]]);
                ptr++;
            }
            int sx = 0;
            for(auto j:join[i]){
                sx++;
                if(samegroup(u[j],v[j]))sx--;
                mergegroup(u[j],v[j]);
            }
            ans[i] = get(x[i]);
            rollback(sx);
        }
    }
    for(int i = 1;i<=q;i++){
        if(ans[i]!=-1)cout<<ans[i]<<"\n";
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             while(ptr<unchanged.size()&&cost[unchanged[ptr]]>=z[i]){
      |                   ~~~^~~~~~~~~~~~~~~~~

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