Submission #756648

#	Time	Username	Problem	Language	Result	Execution time	Memory
756648		khoquennguoiminhthuong	Bridges (APIO19_bridges)	C++17	44 / 100	3032 ms	11656 KiB

bridges

#include <bits/stdc++.h>

using namespace std;
int n,m,q;
struct canh {
    int u,v,w;
} e[500005];
struct roll {
    int type,u,pa;
};
int goc[500005];
int sz[500005];
int dd[500005];
stack<pair<int,pair<int,int>>>st;
void gop(int u,int v,int type) {
    st.push({type,{u,goc[u]}});
    goc[u]=v;
}
int ans[500005];
int gopgoc(int u) {
    if(goc[u]==0)return u;
    gop(u,gopgoc(goc[u]),0);
    return goc[u];
}
void add(int u,int v) {
    u=gopgoc(u);
    v=gopgoc(v);
    if(u==v)return ;
    sz[u]+=sz[v];
    gop(v,u,1);
}
void rollback(int k) {
    while(st.size()>k) {
        pair<int,pair<int,int>>vv=st.top();
        st.pop();
        if(vv.first==1)sz[goc[vv.second.first]]-=sz[vv.second.first];
        goc[vv.second.first]=vv.second.second;
    }
}
bool cmp(int a,int b) {
    if(e[a].w!=e[b].w)return e[a].w>e[b].w;
    return a<b;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    for(int i=1; i<=n; i++)sz[i]=1;
    cin>>q;
    for(int i=1; i<=q; i++)
        cin>>e[i+m].u>>e[i+m].v>>e[i+m].w;
    int blsize=1000;
    for(int l=m+1; l<=q+m; l+=blsize) {
        int r=min(l+blsize-1,m+q);
        rollback(0);
        vector<int>change;
        vector<int>unchange;
        for(int i=l; i<=r; i++) {
            if(e[i].u==1) {
                change.push_back(i);
                dd[e[i].v]=1;
            } else unchange.push_back(i);
        }
        for(int i=1; i<=m; i++)if(dd[i]==0)unchange.push_back(i);
            else dd[i]=0;
        sort(unchange.begin(),unchange.end(),cmp);
        reverse(change.begin(),change.end());
        for(auto v:unchange) {
            if(v<=m) {
                add(e[v].u,e[v].v);
            } else {
                int now=st.size();
                for(auto vv:change) {
                    if(vv<=v&&dd[e[vv].v]==0) {
                        dd[e[vv].v]=1;
                        int id=e[vv].v;
                        if(e[vv].w>=e[v].w)add(e[id].u,e[id].v);
                    }
                }
                for(auto vv:change) {
                    if(vv>v&&dd[e[vv].v]==0) {
                        int id=e[vv].v;
                        if(e[id].w>=e[v].w)add(e[id].u,e[id].v);
                    }
                }
                ans[v]=sz[gopgoc(e[v].v)];
                rollback(now);
                for(auto vv:change)dd[e[vv].v]=0;
            }
        }
     for(int i=l;i<=r;i++)if(e[i].u==1){int id=e[i].v;e[id].w=e[i].w;}
    }
    for(int i=m+1; i<=m+q; i++)if(ans[i])cout<<ans[i]<<'\n';
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:33:20: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |     while(st.size()>k) {
      |           ~~~~~~~~~^~

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