Submission #1252019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252019		quocbaoo	Bridges (APIO19_bridges)	C++20	59 / 100	3091 ms	5700 KiB

bridges

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int N=5e4;
struct Node{
    int fi,se,ba;
};
stack<Node> st;
int sz[N+5],par[N+5],u[N*2+5],v[N*2+5],w[N*2+5],t[N*2+5],kq[N*2+5];
int b[N*2+5],r[N*2+5],d[N*2+5],s[N*2+5],mp[N*2+5];
bool cmp(pair<int,int> u1,pair<int,int> v1){
    return u1.fi>v1.fi;
}
int fd(int x){
    if (x==par[x]) return x;
    return fd(par[x]);
}
void gop(int x,int y,int ok){
    x=fd(x);y=fd(y);
    if (x==y) return;
    if (sz[x]<sz[y]) swap(x,y);
    if (ok==1){
        st.push({x,sz[x],par[x]});
        st.push({y,sz[y],par[y]});
    }
    sz[x]+=sz[y];par[y]=x;
}
int main(){
    if (fopen("bridges.inp","r")){
        freopen("bridges.inp","r",stdin);
        freopen("bridges.out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m;cin>>n>>m;
    for (int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>w[i];
    }
    int q;cin>>q;
    for (int i=1;i<=q;i++){
        cin>>t[i];
        if (t[i]==1) cin>>b[i]>>r[i];
        else cin>>s[i]>>d[i];
    }
    int sq=int(sqrt(q));
    for (int i=1;i<=q;i++){
        int j=min(i+sq,q);
        vector<int> v1;vector<pair<int,int>> v2;
        for (int i=1;i<=m;i++) mp[i]=0;
        for (int k=i;k<=j;k++){
            if (t[k]==1) v1.push_back(k),mp[b[k]]++;else v2.push_back({d[k],k});
        }
        sort(v2.begin(),v2.end(),cmp);
        vector<pair<int,int>> zz;
        for (int i=1;i<=m;i++){
            if (mp[i]==0) zz.push_back({w[i],i});
        }
        sort(zz.begin(),zz.end(),cmp);
        int bd=0;
        for (int i=1;i<=n;i++) sz[i]=1,par[i]=i;
        for (auto z:v2){
            for (auto k:v1) mp[b[k]]=0;
            while (bd<zz.size()&&w[zz[bd].se]>=z.fi){
                gop(u[zz[bd].se],v[zz[bd].se],0);
                bd++;
            }
            for (int k=v1.size()-1;k>=0;k--){
                if (mp[b[v1[k]]]==0&&v1[k]<z.se){
                    mp[b[v1[k]]]=1;
                    if (r[v1[k]]>=z.fi) gop(u[b[v1[k]]],v[b[v1[k]]],1);
                }
            }
            for (int k=v1.size()-1;k>=0;k--){
                if (mp[b[v1[k]]]==0){
                    mp[b[v1[k]]]=1;
                    if (w[b[v1[k]]]>=z.fi) gop(u[b[v1[k]]],v[b[v1[k]]],1);
                }
            }
            kq[z.se]=sz[fd(s[z.se])];
            while (!st.empty()){
                int su=st.top().fi,kt=st.top().se,pa=st.top().ba;
                st.pop();
                sz[su]=kt;par[su]=pa;
            }
        }
        for (int k=i;k<=j;k++){
            if (t[k]==1) w[b[k]]=r[k];
        }
        i=j;
    }
    // sort cau giam dan cau>=xe
    for (int i=1;i<=q;i++) if (t[i]==2) cout<<kq[i]<<'\n';
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen("bridges.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen("bridges.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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