Submission #1087146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087146		alexander707070	Bridges (APIO19_bridges)	C++14	13 / 100	667 ms	524288 KiB

bridges

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

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=m,tt;
            while(l+1<r){
                tt=(l+r)/2;
                if(getmin(1,1,m,l,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+1)<<"\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();
    }

    return 0;
}

Compilation message (stderr)

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

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