Submission #432957

#	Time	Username	Problem	Language	Result	Execution time	Memory
432957		TLP39	Bridges (APIO19_bridges)	C++14	16 / 100	871 ms	10688 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;

int n,m,q;
int seg[200012]={};
int a[50003];
vector<pair<int,int>> adj[50003];
bool mark[1003];

int bfs(int v,int w)
{
    for(int i=0;i<1003;i++) mark[i]=false;
    int ans=1;
    queue<int> qq;
    qq.push(v);
    mark[v]=true;
    int fr;
    while(!qq.empty())
    {
        fr=qq.front();
        qq.pop();
        for(int i=0;i<adj[fr].size();i++)
        {
            if(a[adj[fr][i].second]>w) continue;
            if(mark[adj[fr][i].first]) continue;
            mark[adj[fr][i].first]=true;
            ans++;
            qq.push(adj[fr][i].first);
        }
    }
    return ans;
}

void solve_1()
{
int t,u,v;
    while(q--)
        {
            scanf("%d %d %d",&t,&u,&v);
            if(t==1)
            {
                a[u]=v;
            }
            else
            {
                printf("%d\n",bfs(u,v));
            }
        }
}

void build(int v,int st,int ed)
{
    if(st==ed)
    {
        seg[v]=a[st];
        return;
    }
    int mid=(st+ed)>>1;
    build(v<<1,st,mid);
    build(1+(v<<1),mid+1,ed);
    seg[v]=min(seg[v<<1],seg[1+(v<<1)]);
}

void upd(int v,int l,int r,int pos,int val)
{
    if(l==r)
    {
        seg[v]=val;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=pos) upd(v<<1,l,mid,pos,val);
    else upd(1+(v<<1),mid+1,r,pos,val);
    seg[v]=min(seg[v<<1],seg[1+(v<<1)]);
}

int que(int v,int l,int r,int st,int ed)
{
    if(st>ed) return 1000000001;
    if(l==st && r==ed) return seg[v];
    int mid=(l+r)>>1;
    return min(que(v<<1,l,mid,st,min(mid,ed)),que(1+(v<<1),mid+1,r,max(mid+1,st),ed));
}


int getlow(int x,int w)
{
    if(x==1) return 1;
    int hi=x,low=1,av;
    while(hi>low)
    {
        av=(hi+low)>>1;
        if(que(1,1,m,av,x-1)>=w) hi=av;
        else low=av+1;
    }
    return hi;
}

int gethi(int x,int w)
{
    if(x==n) return n;
    int low=x,hi=n,av;
    while(hi>low)
    {
        av=(hi+low+1)>>1;
        if(que(1,1,m,x,av-1)>=w) low=av;
        else hi=av-1;
    }
    return hi;
}

    int main()
    {
        scanf("%d %d",&n,&m);
        int t1,t2;
        int t,u,v;
        for(int i=1;i<=m;i++)
        {
            scanf("%d %d %d",&t1,&t2,&a[i]);
            adj[t1].push_back({t2,i});
            adj[t2].push_back({t1,i});
        }
        if(n==1)
        {
            scanf("%d",&q);
            while(q--)
            {
                scanf("%d %d %d",&t,&u,&v);
                if(t==2) printf("1\n");
            }
            return 0;
        }
        build(1,1,m);
        scanf("%d",&q);
        if(n<=1000 && m<=1000 && q<=10000)
        {
            solve_1();
            return 0;
        }
        while(q--)
        {
            scanf("%d %d %d",&t,&u,&v);
            if(t==1)
            {
                upd(1,1,m,u,v);
            }
            else
            {
                printf("%d\n",gethi(u,v)-getlow(u,v)+1);
            }
        }
    }

Compilation message (stderr)

bridges.cpp: In function 'int bfs(int, int)':
bridges.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int i=0;i<adj[fr].size();i++)
      |                     ~^~~~~~~~~~~~~~~
bridges.cpp: In function 'void solve_1()':
bridges.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |             scanf("%d %d %d",&t,&u,&v);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         scanf("%d %d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:121:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |             scanf("%d %d %d",&t1,&t2,&a[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:127:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |             scanf("%d",&q);
      |             ~~~~~^~~~~~~~~
bridges.cpp:130:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |                 scanf("%d %d %d",&t,&u,&v);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~
bridges.cpp:136:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         scanf("%d",&q);
      |         ~~~~~^~~~~~~~~
bridges.cpp:144:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |             scanf("%d %d %d",&t,&u,&v);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~

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