Submission #552775

#	Time	Username	Problem	Language	Result	Execution time	Memory
552775		jjaewon	Bridges (APIO19_bridges)	C++14	100 / 100	2378 ms	12304 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define endl '\n'
#define y1 holyshit
#define all(x) x.begin(),x.end()
const int inf=0x3f3f3f3f;

#define SZ 700

struct DATA{
    //type 0: edge, type 1: query 1, type 2: query 2
    int type,idx,u,v,d;
    bool operator<(const DATA& p) const{ return d==p.d?type>p.type:d<p.d; }
}edge[100010];
vector<DATA> query;
int N,M,Q,ans[100010];

int p[50010],sz[50010];
stack<pii> st;
int find(int x){ return x==p[x]?x:find(p[x]); }
void merge(int x,int y,bool undo){
    x=find(x); y=find(y);
    if(x==y) return;
    if(sz[x]<sz[y]) swap(x,y);
    sz[x]+=sz[y];
    p[y]=x;
    if(undo) st.push({x,y});
}

void solve(){
    vector<DATA> v;
    vector<int> md;
    bool used[100010]={0};
    int w[100010];
    for(auto i:query){
        if(i.type==1) used[i.u]=1;
        else if(i.type==2) v.push_back(i);
    }
    for(int i=1;i<=M;i++){
        if(!used[i]) v.push_back(edge[i]);
        else{
            md.push_back(i);
            w[i]=edge[i].d;
        }
    }
    sort(all(v));
    reverse(all(v));
    for(int i=1;i<=N;i++) p[i]=i, sz[i]=1;
    for(auto i:v){
        if(i.type==0){
            merge(i.u,i.v,0);
            //cout<<"set "<<i.u<<' '<<i.v<<' '<<i.d<<endl;
        }
        else{
            //cout<<'#'<<' '<<i.idx<<endl;
            for(auto j:query){
                if(i.idx==j.idx) break;
                if(j.type==1) w[j.u]=j.d;
            }
            for(auto j:md) if(w[j]>=i.d){
                merge(edge[j].u,edge[j].v,1);
                //cout<<"add "<<edge[j].u<<' '<<edge[j].v<<' '<<w[j]<<endl;
            }
            ans[i.idx]=sz[find(i.u)];
            //cout<<"ans: "<<ans[i.idx]<<endl;
            for(auto j:md) w[j]=edge[j].d;
            while(!st.empty()){
                auto [x,y]=st.top();
                sz[x]-=sz[y];
                p[y]=y;
                st.pop();
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(int i=1;i<=M;i++){
        int u,v,d; cin>>u>>v>>d;
        edge[i]={0,i,u,v,d};
    }
    cin>>Q;
    for(int i=1;i<=Q;i++){
        int t,a,b; cin>>t>>a>>b;
        query.push_back({t,i,a,0,b});
        if(i%SZ==0){
            solve();
            for(auto j:query) if(j.type==1) edge[j.u].d=j.d;
            query.clear();
        }
    }
    solve();
    for(int i=1;i<=Q;i++) if(ans[i]>0) cout<<ans[i]<<endl;
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void solve()':
bridges.cpp:73:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |                 auto [x,y]=st.top();
      |                      ^

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