Submission #440401

#	Time	Username	Problem	Language	Result	Execution time	Memory
440401		VladM	Bridges (APIO19_bridges)	C++14	29 / 100	1183 ms	5452 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

#define DIM 50007

#define INF 1000000007

typedef pair<long long, long long> pll;

long long vis[DIM], res, n, m, u, v, w[DIM], t[4*DIM], it, s, W, l, r, mid, L, R, mn, q, T;

vector<pll> vec[DIM];

void BuildTree(long long v, long long tl, long long tr)
{
    if(tl==tr)
    {
        t[v]=w[tl];
        return;
    }
    long long tm=(tl+tr)>>1;
    BuildTree(2*v+1, tl, tm);
    BuildTree(2*v+2, tm+1, tr);
    t[v]=min(t[2*v+1], t[2*v+2]);
    return;
}

void update(long long v, long long tl, long long tr, long long x, long long val)
{
    if(x<tl || tr<x) return;
    if(tl==tr)
    {
        t[v]=val;
        return;
    }
    long long tm=(tl+tr)>>1;
    update(2*v+1, tl, tm, x, val);
    update(2*v+2, tm+1, tr, x, val);
    t[v]=min(t[2*v+1], t[2*v+2]);
    return;
}

long long get_min(long long v, long long tl, long long tr, long long L, long long R)
{
    if(tr<L || R<tl) return INF;
    if(L<=tl && tr<=R) return t[v];
    long long tm=(tl+tr)>>1;
    long long mn1=get_min(2*v+1, tl, tm, L, R);
    long long mn2=get_min(2*v+2, tm+1, tr, L, R);
    return min(mn1, mn2);
}

void dfs(long long v, long long car)
{
    vis[v]=1;
    for(auto to : vec[v])
    {
        if(vis[to.first]==1 || w[to.second]<car) continue;
        dfs(to.first, car);
    }
    return;
}

void solve()
{
    for(int i=1; i<=m; i++)
    {
        cin>>u>>v>>w[i];
        vec[u].push_back({v, i});
        vec[v].push_back({u, i});
    }
    cin>>q;
    while(q--)
    {
        cin>>T;
        if(T==1)
        {
            cin>>it>>r;
            w[it]=r;
            continue;
        }
        cin>>s>>W;
        for(int i=1; i<=n; i++) vis[i]=0;
        vis[s]=1;
        dfs(s, W);
        res=0;
        for(int i=1; i<=n; i++) res+=vis[i];
        cout<<res<<endl;
    }
    return;
}

int main()
{
    cin>>n>>m;
    if(n<=1000 && m<=1000)
    {
        solve();
        return 0;
    }
    for(int i=1; i<=m; i++)
    {
        cin>>u>>v>>w[i];
    }
    if(n!=1) BuildTree(0, 1, m);
    cin>>q;
    while(q--)
    {
        cin>>T;
        if(T==1)
        {
            cin>>it>>r;
            if(n!=1) update(0, 1, m, it, r);
            continue;
        }
        cin>>s>>W;
        if(n==1)
        {
            cout<<1<<endl;
            continue;
        }
        if(s==n) R=n;
        else
        {
            l=s;
            r=m;
            while(l<r)
            {
                mid=(l+r+1)>>1;
                mn=get_min(0, 1, m, s, mid);
                if(mn<W) r=mid-1;
                else l=mid;
            }
            if(l==s)
            {
                mn=get_min(0, 1, m, s, s);
                if(mn>=W) R=s+1;
                else R=s;
            }
            else
            {
                R=l+1;
            }
        }
        if(s==1) L=1;
        else
        {
            l=1;
            r=s-1;
            while(l<r)
            {
                mid=(l+r)>>1;
                mn=get_min(0, 1, m, mid, s-1);
                if(mn<W) l=mid+1;
                else r=mid;
            }
            if(l==s-1)
            {
                mn=get_min(0, 1, m, l, l);
                if(mn<W) L=s;
                else L=s-1;
            }
            else L=l;
        }
        cout<<R-L+1<<endl;
    }
    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