Submission #1087168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087168		alexander707070	Bridges (APIO19_bridges)	C++14	43 / 100	603 ms	25040 KiB

bridges

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

struct query{
    int s,w,id;

    inline friend bool operator < (query fr,query sc){
        return fr.w<sc.w;
    }
}qs[MAXN],e[MAXN];

int n,m,q,a[MAXN],b[MAXN],c[MAXN];
int type[MAXN],s[MAXN],w[MAXN];

int cnt;
vector<int> weights;
unordered_map<int,int> mp;

vector< pair<int,int> > v[MAXN];

int tim,li[MAXN];

int dfs(int x,int w){
    li[x]=tim;

    int res=1;
    for(int i=0;i<v[x].size();i++){
        if(li[v[x][i].first]==tim or c[v[x][i].second]<w)continue;
        res+=dfs(v[x][i].first,w);
    }

    return res;
}

void solve_small(){
    for(int i=1;i<=q;i++){
        if(type[i]==1){
            c[s[i]]=w[i];
        }else{
            tim++;
            cout<<dfs(s[i],w[i])<<"\n";
        }
    }
}

int tree[4*MAXN];

void update(int v,int l,int r,int pos,int val){
    if(l==r){
        tree[v]=val;
    }else{
        int tt=(l+r)/2;
        if(pos<=tt)update(2*v,l,tt,pos,val);
        else update(2*v+1,tt+1,r,pos,val);

        tree[v]=min(tree[2*v],tree[2*v+1]);
    }
}

int getmin(int v,int l,int r,int ll,int rr){
    if(ll>rr)return n+m+q;
    if(l==ll and r==rr){
        return tree[v];
    }else{
        int tt=(l+r)/2;
        return min( getmin(2*v,l,tt,ll,min(tt,rr)) , getmin(2*v+1,tt+1,r,max(tt+1,ll),rr) );
    }
}

void solve_line(){
    for(int i=1;i<=m;i++){
        update(1,1,m,i,c[i]);
    }

    for(int i=1;i<=q;i++){
        if(type[i]==1){
            update(1,1,m,s[i],w[i]);
        }else{
            int l=s[i]-1,r=n,tt;
            while(l+1<r){
                tt=(l+r)/2;
                if(getmin(1,1,m,s[i],tt)>=w[i]){
                    l=tt;
                }else{
                    r=tt;
                }
            }

            int to=l;

            l=0; r=s[i];
            while(l+1<r){
                tt=(l+r)/2;
                if(getmin(1,1,m,tt,s[i]-1)>=w[i]){
                    r=tt;
                }else{
                    l=tt;
                }
            }

            int from=r;

            cout<<max(0,to-from+2)<<"\n";
        }
    }
}

int dsu[MAXN],sz[MAXN],ans[MAXN];

int root(int x){
    if(dsu[x]==x)return x;
    dsu[x]=root(dsu[x]);
    return dsu[x];
}

void mergev(int x,int y){
    int rootx=root(x);
    int rooty=root(y);

    if(rootx==rooty)return;
    if(sz[rootx]<sz[rooty])swap(rootx,rooty);

    sz[rootx]+=sz[rooty];
    dsu[rooty]=rootx;
}

void solve_static(){
    for(int i=1;i<=q;i++){
        qs[i]={s[i],w[i],i};
    }

    for(int i=1;i<=m;i++){
        e[i]={a[i],c[i],b[i]};
    }

    for(int i=1;i<=n;i++){
        dsu[i]=i; sz[i]=1;
    }

    sort(qs+1,qs+q+1);
    sort(e+1,e+m+1);

    int pt=m;
    for(int i=q;i>=1;i--){
        while(pt>=1 and e[pt].w>=qs[i].w){
            mergev(e[pt].s,e[pt].id); pt--;
        }

        ans[qs[i].id]=sz[root(qs[i].s)];
    }

    for(int i=1;i<=q;i++){
        cout<<ans[i]<<"\n";
    }
}

int main(){

    cin>>n>>m;

    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i]>>c[i];
        weights.push_back(c[i]);

        v[a[i]].push_back({b[i],i});
        v[b[i]].push_back({a[i],i});
    }

    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>type[i]>>s[i]>>w[i];
        weights.push_back(w[i]);
    }

    sort(weights.begin(),weights.end());
    for(int i=0;i<weights.size();i++){
        if(i==0 or weights[i]!=weights[i-1])cnt++;
        mp[weights[i]]=cnt;
    }

    for(int i=1;i<=m;i++)c[i]=mp[c[i]];
    for(int i=1;i<=q;i++)w[i]=mp[w[i]];

    if(n<=1000 and m<=1000 and q<=10000){
        solve_small();
    }else if(m==n-1){
        solve_line();
    }else{
        solve_static();
    }

    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int dfs(int, int)':
bridges.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:177:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for(int i=0;i<weights.size();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