Submission #721504

#	Time	Username	Problem	Language	Result	Execution time	Memory
721504		victor_gao	Bridges (APIO19_bridges)	C++17	0 / 100	2452 ms	422388 KiB

bridges

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 50015
#define M 100015
#define B 400
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct dsu_data{
    int a,sz1,b,sz2;
    dsu_data(int _a,int _sz1,int _b,int _sz2):a(_a),sz1(_sz1),b(_b),sz2(_sz2){}
};
struct dsu{
    int boss[N],sz[N],group;
    stack<dsu_data>st;
    void init(int n){
        for (int i=0;i<=n+2;i++){
            boss[i]=i; sz[i]=1;
        }
    }
    int find(int x){
        if (boss[x]==x) return x;
        return find(boss[x]);
    }
    void Merge(int a,int b){
        int u=find(a),v=find(b);
        st.push(dsu_data(u,sz[u],v,sz[v]));
        if (u==v) return;
        if (sz[u]<sz[v]) swap(u,v);
        boss[v]=u;
        sz[u]+=sz[v];
    }
    void rollback(){
        if (st.empty()) return;
        dsu_data np=st.top(); st.pop();
        if (np.a==np.b) return;
        group++;
        boss[np.a]=np.a;
        sz[np.a]=np.sz1;
        boss[np.b]=np.b;
        sz[np.b]=np.sz2;
    }
    void undo(int t){
        while (st.size()>t)
            rollback();
    }
}dsu;
struct Query{
    int type,a,b;
    Query(int x,int y,int z):type(x),a(y),b(z){}
};
struct Edge{
    int u,v,c,i;
    bool operator<(const Edge a)const{
        if (c!=a.c) return c>a.c;
        return i<a.i;
    }
};
vector<Query>qry;
vector<pii>now;
vector<int>have_use,op[M];
Edge E[M];
set<Edge>all;
int n,m,q,ans[M];
bool vis[M];
bool cmp(pii a,pii b){
    if (a.x!=b.x) return a.x>b.x;
    return a.y<b.y;
}
void solve(){
    auto it=all.begin();
    for (auto [c,id]:now){
        int pos=qry[id].a;
        while (it!=all.end()&&(*it).c>=c){
            dsu.Merge((*it).u,(*it).v);
            it++;
        }
        int t=dsu.st.size();
        for (auto i:have_use){
            int last=-1e9;
            for (auto j:op[i]){
                if (j<=id)
                    last=qry[j].b;
            }
            if (last<0){
                if (E[i].c>=c)
                    dsu.Merge(E[i].u,E[i].v);
            }
            else if (last>=c)
                dsu.Merge(E[i].u,E[i].v);
        }
        ans[id]=dsu.sz[dsu.find(pos)];
        dsu.undo(t);
    }
}
signed main(){
    fast
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        cin>>E[i].u>>E[i].v>>E[i].c;
        E[i].i=i;
        all.insert(E[i]);
    }
    cin>>q;
    for (int i=1;i<=q;i++){
        int x,y,z; cin>>x>>y>>z;
        qry.push_back(Query(x,y,z));
    }
    for (int i=0;i<q;i+=B){
        for (int j=0;j<B&&j+i<q;j++){
            if (qry[j].type==1){
                int e=qry[j].a;
                op[e].push_back(j);
                if (!vis[e]){
                    vis[e]=1;
                    have_use.push_back(e);
                    all.erase(E[e]);
                }
            }
            else now.push_back({qry[j].b,j});
        }
        dsu.init(n);
        sort(now.begin(),now.end(),cmp);
        solve();
        for (int j=0;j<B&&j+i<q;j++){
            if (qry[j].type==1){
                int e=qry[j].a;
                op[e].pop_back();
                if (all.find(E[e])!=all.end())
                    all.erase(E[e]);
                E[e].c=qry[j].b;
                all.insert(E[e]);
                vis[e]=0;
            }
        }
        have_use.clear();
        now.clear();
    }
    for (int i=0;i<q;i++)
        if (ans[i])
            cout<<ans[i]<<"\n";
}

Compilation message (stderr)

bridges.cpp: In member function 'void dsu::undo(int)':
bridges.cpp:53:25: warning: comparison of integer expressions of different signedness: 'std::stack<dsu_data>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |         while (st.size()>t)
      |                ~~~~~~~~~^~

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