Submission #432914

#	Time	Username	Problem	Language	Result	Execution time	Memory
432914		Amylopectin	Bridges (APIO19_bridges)	C++14	0 / 100	271 ms	524292 KiB

bridges

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
const int mxn = 2e6 + 10,mxi = 0;
struct we
{
    int to,dis;
};
struct pat
{
    int fr,to,fri,toi;
};
struct pat pli[mxn] = {};
vector<struct we> pa[mxn] = {};
int u[mxn] = {},cou,se[mxn] = {},dli[mxn] = {},of;
int fima(int l,int r)
{
    if(l > r)
        return l;
    return r;
}
int fimi(int l,int r)
{
    if(l < r)
        return l;
    return r;
}
int cre(int cl,int cr,int no)
{
    if(cl == cr)
    {
        se[no] = dli[cl];
        return 0;
    }
    int mid = (cl + cr) / 2;
    cre(cl,mid,no*2);
    cre(mid+1,cr,no*2+1);
    se[no] = fimi(se[no*2],se[no*2+1]);
//    se[no] = mxi;
    return 0;
}
int ins(int cl,int cr,int no,int tn,int iva)
{
    if(cr < tn || cl > tn)
    {
//        se[no] = iva;
        return 0;
    }
    if(cl == cr)
    {
        se[no] = iva;
        return 0;
    }
    int mid = (cl + cr) / 2;
    ins(cl,mid,no*2,tn,iva);
    ins(mid+1,cr,no*2+1,tn,iva);
    se[no] = fimi(se[no*2],se[no*2+1]);
    return 0;
}
int nle(int cl,int cr,int no,int tn,int iva)
{
    if(cr < tn)
    {
        return mxi;
    }
    if(cl == cr)
    {
        if(se[no] >= iva)
        {
            return 0;
        }
        of = 1;
        return cl;
    }
    int mid = (cl+cr) / 2,cn;
    if(cl < tn)
    {
        cn = nle(cl,mid,no*2,tn,iva);
        if(of == 1)
        {
            return cn;
        }
        return nle(mid+1,cr,no*2+1,tn,iva);
    }
    else
    {
        if(se[no*2] >= iva)
        {
           return nle(mid+1,cr,no*2+1,tn,iva);
        }
        else
        {
            return nle(cl,mid,no*2,tn,iva);
        }
    }
//    return 0;
}
int nri(int cl,int cr,int no,int tn,int iva)
{
    if(cl > tn)
    {
        return mxi;
    }
    if(cl == cr)
    {
        if(se[no] >= iva)
        {
            return 0;
        }
        of = 1;
        return cl;
    }
    int mid = (cl+cr) / 2,cn;
    if(cr > tn)
    {
        cn = nri(mid+1,cr,no*2+1,tn,iva);
        if(of == 1)
        {
            return cn;
        }
        return nri(cl,mid,no*2,tn,iva);
    }
    else
    {
        if(se[no*2+1] >= iva)
        {
           return nri(cl,mid,no*2,tn,iva);
        }
        else
        {
            return nri(mid+1,cr,no*2+1,tn,iva);
        }
    }
//    return 0;
}
int re(int cn,int wei,int fla)
{
    int i,fn;
    u[cn] = fla;
    cou ++;
    for(i=0; i<pa[cn].size(); i++)
    {
        fn = pa[cn][i].to;
        if(u[fn] == fla || pa[cn][i].dis < wei)
        {
            continue;
        }
        re(fn,wei,fla);
    }
    return 0;
}
int main()
{
    int i,j,n,m,f,t,cdi,cn,fn,q,cst,cl,cr;
    scanf("%d %d",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d %d",&f,&t,&cdi);
        dli[i] = cdi;
//        pli[i] = {f,t,pa[f].size(),pa[t].size()};
//        pa[f].push_back({t,cdi});
//        pa[t].push_back({f,cdi});
    }
    cre(1,m,1);
    scanf("%d",&q);
    for(i=1; i<=q; i++)
    {
        scanf("%d %d %d",&cst,&f,&t);
        if(cst == 1)
        {
            ins(1,m,1,f,t);
//            pa[pli[f].fr][pli[f].fri].dis = t;
//            pa[pli[f].to][pli[f].toi].dis = t;
        }
        else
        {
            cou = 0;
            if(f == 1)
            {
                of = 0;
                cr = nle(1,m,1,f,t);
                if(of == 0)
                {
                    cr = n;
                }
                cou = cr;
            }
            else if(f == n)
            {
                of = 0;
                cl = nri(1,m,1,f-1,t);
                if(of == 0)
                {
                    cl = 0;
                }
                cou = n-cl;
            }
            else
            {
                of = 0;
                cl = nri(1,m,1,f-1,t);
                if(of == 0)
                {
                    cl = 0;
                }
                of = 0;
                cr = nle(1,m,1,f,t);
                if(of == 0)
                {
                    cr = n;
                }
                cou = cr - cl;
            }
//            cr = nle()
//            re(f,t,i);
            printf("%d\n",cou);
        }
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int re(int, int, int)':
bridges.cpp:142:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<we>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(i=0; i<pa[cn].size(); i++)
      |              ~^~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:155:11: warning: unused variable 'j' [-Wunused-variable]
  155 |     int i,j,n,m,f,t,cdi,cn,fn,q,cst,cl,cr;
      |           ^
bridges.cpp:155:25: warning: unused variable 'cn' [-Wunused-variable]
  155 |     int i,j,n,m,f,t,cdi,cn,fn,q,cst,cl,cr;
      |                         ^~
bridges.cpp:155:28: warning: unused variable 'fn' [-Wunused-variable]
  155 |     int i,j,n,m,f,t,cdi,cn,fn,q,cst,cl,cr;
      |                            ^~
bridges.cpp:156:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:159:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         scanf("%d %d %d",&f,&t,&cdi);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:166:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
bridges.cpp:169:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         scanf("%d %d %d",&cst,&f,&t);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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