Submission #955513

#	Time	Username	Problem	Language	Result	Execution time	Memory
955513		bunhadasou	Bridges (APIO19_bridges)	C++14	43 / 100	598 ms	10320 KiB

bridges

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define PB push_back
#define EB emplace_back
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#define ll long long
#define sz(x) (int)x.size()
#define TASK "cf"

using namespace std;


const int maxn=1e5+5;
vector<pair<pair<int,int>,int>> ds,query;
int par[maxn],Rank[maxn];
int n,m,q;
int T[2][4*maxn];
int ans[maxn];


//subtask
int X[maxn],Y[maxn],Z[maxn];
int Q_x[maxn],Q_y[maxn],Q_z[maxn];


void make_set1(){
    for (int i=1;i<=n;i++) {
        par[i]=i;
        Rank[i]=1;
    }
}

int find1(int x) {
    if (x==par[x]) return x; return par[x]=find1(par[x]);
}

void UNION1(int x,int y){
    x=find1(x);y=find1(y);
    if (x==y) return ;
    if (Rank[x]<Rank[y]) swap(x,y);
    Rank[x]+=Rank[y];
    par[y]=x;
    return ;
}

void subtask1(){
    ds.resize(m+1);
    for (int i=1;i<=m;i++) {
        ds[i]=mp(mp(X[i],Y[i]),Z[i]);
    }
    for (int i=1;i<=q;i++) {
        int type=Q_x[i],x=Q_y[i],y=Q_z[i];
        if (type==1) {
            ds[x].se=y;
        }
        else {
            make_set1();
            for (int i=1;i<=m;i++) {
                if (ds[i].se>=y) UNION1(ds[i].fi.fi,ds[i].fi.se);
            }
            cout<<Rank[find1(x)]<<"\n";
        }
    }
}


void update(int rev,int node,int l,int r,int u,int v,int val) {
    if (u>r|| v<l) return ;
    if (u<=l&& r<=v) {
        T[rev][node]=val; return ;
    }
    int mid=l+r>>1;
    update(rev,node<<1,l,mid,u,v,val);
    update(rev,node<<1|1,mid+1,r,u,v,val);
    T[rev][node]=min(T[rev][node<<1],T[rev][node<<1|1]);
}

int get(int rev,int node,int l,int r,int u,int v) {
    if (u>r||v<l) return 1e9+9;
    if (u<=l&&r<=v) return T[rev][node];
    int mid=l+r>>1;
    return min(get(rev,node<<1,l,mid,u,v),get(rev,node<<1|1,mid+1,r,u,v));
}

int tim1(int pos,int val) {
    int lo=1,hi=pos-1;
    if (hi<lo || hi<1) return pos;
    int res=pos;
    while(hi-lo>=0){
        int mid=hi+lo>>1;
        if (get(0,1,1,n,mid,pos-1)>=val){
            res=mid;
            hi=mid-1;
        }
        else lo=mid+1;
    }
    return res;
}

int tim2(int pos,int val) {
    int lo=pos+1,hi=n;
    if (hi<lo || lo>n) return pos;
    int res=pos;
    while(hi-lo>=0){
        int mid=hi+lo>>1;
        if (get(1,1,1,n,pos+1,mid)>=val){
            res=mid;
            lo=mid+1;
        }
        else hi=mid-1;
    }
    return res;
}

void subtask2(){
    ds.resize(m+1);
    for (int i=1;i<=m;i++) {
        ds[i]=mp(mp(X[i],Y[i]),Z[i]);
    }
    for (int i=1;i<=m;i++) {
        int u=ds[i].fi.fi,v=ds[i].fi.se,w=ds[i].se;
        update(0,1,1,n,u,u,w);
        update(1,1,1,n,v,v,w);
    }
    for (int i=1;i<=q;i++) {
        int type=Q_x[i],x=Q_y[i],y=Q_z[i];
        if (type==1){
            int u=ds[x].fi.fi,v=ds[x].fi.se;
            ds[x].se=y;
            update(0,1,1,n,u,u,y);
            update(1,1,1,n,v,v,y);
        }
        else {
            int lo=tim1(x,y),hi=tim2(x,y);
            cout<<hi-lo+1<<"\n";
        }
    }
}



void make_set3(){
    for (int i=1;i<=n;i++) {
        par[i]=i;
        Rank[i]=1;
    }
}

int find3(int x) {
    if (x==par[x]) return x; return par[x]=find3(par[x]);
}

void UNION3(int x,int y) {
    x=find3(x);y=find3(y);
    if (x==y) return ;
    if (Rank[x]<Rank[y]) swap(x,y);
    Rank[x]+=Rank[y];
    par[y]=x;
    return ;
}

bool cmp1(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b){
    return a.se>b.se;
}

bool cmp2(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b){
    return a.fi.se>b.fi.se;
}

void subtask3(){
    make_set3();
    for (int i=1;i<=m;i++) {
        ds.PB(mp(mp(X[i],Y[i]),Z[i]));
    }
    for (int i=1;i<=q;i++) {
        int type=Q_x[i],x=Q_y[i],y=Q_z[i];
        query.PB(mp(mp(x,y),i));
    }
    sort(all(ds),cmp1);
    sort(all(query),cmp2);
    int j=0;
    for (int i=0;i<q;i++) {
        int w=query[i].fi.se;
        while (j<m && ds[j].se>=w) {
            UNION3(ds[j].fi.fi,ds[j].fi.se);
            j++;
        }
        ans[query[i].se]=Rank[find3(query[i].fi.fi)];
    }
    for (int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}



signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int sub2=0;
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        cin>>X[i]>>Y[i]>>Z[i];
        if (X[i]==i && Y[i]==i+1) sub2++;
    }
    cin>>q;
    for (int i=1;i<=q;i++) {
        cin>>Q_x[i]>>Q_y[i]>>Q_z[i];
    }
    if (n<=1000 && m<=1000 && q<=10000) subtask1();
    else if (sub2==m && m==n-1) subtask2();
    else subtask3();




    return 0;

}

Compilation message (stderr)

bridges.cpp: In function 'int find1(int)':
bridges.cpp:37:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   37 |     if (x==par[x]) return x; return par[x]=find1(par[x]);
      |     ^~
bridges.cpp:37:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   37 |     if (x==par[x]) return x; return par[x]=find1(par[x]);
      |                              ^~~~~~
bridges.cpp: In function 'void update(int, int, int, int, int, int, int)':
bridges.cpp:75:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |     int mid=l+r>>1;
      |             ~^~
bridges.cpp: In function 'int get(int, int, int, int, int, int)':
bridges.cpp:84:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |     int mid=l+r>>1;
      |             ~^~
bridges.cpp: In function 'int tim1(int, int)':
bridges.cpp:93:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |         int mid=hi+lo>>1;
      |                 ~~^~~
bridges.cpp: In function 'int tim2(int, int)':
bridges.cpp:108:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |         int mid=hi+lo>>1;
      |                 ~~^~~
bridges.cpp: In function 'int find3(int)':
bridges.cpp:153:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  153 |     if (x==par[x]) return x; return par[x]=find3(par[x]);
      |     ^~
bridges.cpp:153:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  153 |     if (x==par[x]) return x; return par[x]=find3(par[x]);
      |                              ^~~~~~
bridges.cpp: In function 'void subtask3()':
bridges.cpp:179:13: warning: unused variable 'type' [-Wunused-variable]
  179 |         int type=Q_x[i],x=Q_y[i],y=Q_z[i];
      |             ^~~~

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