oj.uz

Submission #432957

# Submission time Handle Problem Language Result Execution time Memory
432957 2021-06-18T15:46:57 Z TLP39 Bridges (APIO19_bridges) C++14
16 / 100
 871 ms 10688 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 3876 KB Output is correct
2 Correct 458 ms 3812 KB Output is correct
3 Correct 447 ms 3776 KB Output is correct
4 Correct 468 ms 3856 KB Output is correct
5 Correct 456 ms 3940 KB Output is correct
6 Correct 532 ms 3908 KB Output is correct
7 Correct 524 ms 4004 KB Output is correct
8 Correct 555 ms 3948 KB Output is correct
9 Correct 33 ms 1628 KB Output is correct
10 Correct 477 ms 3816 KB Output is correct
11 Correct 471 ms 3964 KB Output is correct
12 Correct 871 ms 4168 KB Output is correct
13 Correct 166 ms 3780 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 407 ms 3232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 10688 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 3876 KB Output is correct
2 Correct 458 ms 3812 KB Output is correct
3 Correct 447 ms 3776 KB Output is correct
4 Correct 468 ms 3856 KB Output is correct
5 Correct 456 ms 3940 KB Output is correct
6 Correct 532 ms 3908 KB Output is correct
7 Correct 524 ms 4004 KB Output is correct
8 Correct 555 ms 3948 KB Output is correct
9 Correct 33 ms 1628 KB Output is correct
10 Correct 477 ms 3816 KB Output is correct
11 Correct 471 ms 3964 KB Output is correct
12 Correct 871 ms 4168 KB Output is correct
13 Correct 166 ms 3780 KB Output is correct
14 Incorrect 407 ms 3232 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1356 KB Output isn't correct
2 Halted 0 ms 0 KB -