Submission #933774

#	Time	Username	Problem	Language	Result	Execution time	Memory
933774		irmuun	Bridges (APIO19_bridges)	C++17	29 / 100	496 ms	17732 KiB

bridges

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct segtree{
    ll n;
    vector<ll>d;
    vector<ll>u;
    segtree(ll n):n(n){
        d.resize(4*n);
        build(1,0,n-1);
    }
    void build(ll node,ll l,ll r){
        if(l==r){
            d[node]=0;
            return;
        }
        ll mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=min(d[node*2],d[node*2+1]);
    }
    ll query(ll node,ll l,ll r,ll L,ll R){
        if(l > R || r < L || L > R){
            return 1e18;
        }
        if(L <= l && r <= R){
            return d[node];
        }
        ll mid=(l+r)/2;
        return min(query(node*2,l,mid,L,R),query(node*2+1,mid+1,r,L,R));
    }
    void update(ll node,ll l,ll r,ll k,ll val){
        if(l>k || r<k)return;
        if(l==r){
            d[node]=val;
            return;
        }
        ll mid=(l+r)/2;
        update(node*2,l,mid,k,val);
        update(node*2+1,mid+1,r,k,val);
        d[node]=min(d[node*2],d[node*2+1]);
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m;
    cin>>n>>m;
    multiset<pair<ll,ll>>adj[n];
    vector<array<ll,3>>edge;
    for(ll i=0;i<m;i++){
        ll u,v,d;
        cin>>u>>v>>d;
        u--,v--;
        adj[u].insert({v,d});
        adj[v].insert({u,d});
        edge.pb({u,v,d});
    }
    vector<bool>used(n);
    ll q;
    cin>>q;
    if(n<=1000&&m<=1000&&q<=10000){
        while(q--){
            ll t;
            cin>>t;
            if(t==1){
                ll b,r;
                cin>>b>>r;
                b--;
                auto [u,v,d]=edge[b];
                adj[u].erase(adj[u].find({v,d}));
                adj[v].erase(adj[v].find({u,d}));
                edge[b][2]=r;
                d=r;
                adj[u].insert({v,d});
                adj[v].insert({u,d});
            }
            else{
                ll s,w;
                cin>>s>>w;
                s--;
                fill(all(used),0);
                function <void(ll)> dfs=[&](ll x){
                    used[x]=true;
                    for(auto [y,d]:adj[x]){
                        if(d>=w&&!used[y]){
                            dfs(y);
                        }
                    }
                };
                dfs(s);
                ll ans=0;
                for(ll i=0;i<n;i++){
                    if(used[i]==true){
                        ans++;
                    }
                }
                cout<<ans<<"\n";
            }
        }
        return 0;
    }
    if(m==n-1){
        segtree sg(n);
        for(auto [u,v,d]:edge){
            sg.update(1,0,n-1,min(u,v),d);
        }
        while(q--){
            ll t;
            cin>>t;
            if(t==1){
                ll b,r;
                cin>>b>>r;
                b--;
                ll u=edge[b][0],v=edge[b][1];
                sg.update(1,0,n-1,min(u,v),r);
            }
            else{
                ll s,w;
                cin>>s>>w;
                s--;
                ll l=0,r=s;
                while(l<r){
                    ll mid=(l+r)/2;
                    if(sg.query(1,0,n-1,mid,s-1)>=w){
                        r=mid;
                    }
                    else{
                        l=mid+1;
                    }
                }
                ll ans=s-l+1;
                l=s,r=n-1;
                while(l<r){
                    ll mid=(l+r+1)/2;
                    if(sg.query(1,0,n-1,s,mid-1)>=w){
                        l=mid;
                    }
                    else{
                        r=mid-1;
                    }
                }
                ans+=l-s;
                cout<<ans<<"\n";
            }
        }
        return 0;
    }
}

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