Submission #423374

#	Time	Username	Problem	Language	Result	Execution time	Memory
423374		Amylopectin	Roadside Advertisements (NOI17_roadsideadverts)	C++14	100 / 100	116 ms	15784 KiB

roadsideadverts

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
const int mxn = 1e5 + 10,mxi = 1e9 + 10;
struct we
{
    int to,dis;
};
vector <struct we> pat[mxn] = {};
struct we par[30][mxn] = {};
int ru = 1,hii[mxn] = {},cus[mxn] = {},tw[30] = {},bdi;
int re(int cn,int be,int la)
{
    int i,fn;
    hii[cn] = la;
//    pa[0][cn] = {be,};
    for(i=0; i<pat[cn].size(); i++)
    {
        fn = pat[cn][i].to;
        if(fn == be)
        {
            continue;
        }
        par[0][fn] = {cn,pat[cn][i].dis};
        re(fn,cn,la+1);
    }
    return 0;
}
int lca(int l,int r)
{
    int f,dif,i,j,cva,su = 0;
    if(hii[l] > hii[r])
    {
        f = l;
        l = r;
        r = f;
    }
    dif = hii[r] - hii[l];
    for(i=ru-1; i>=0; i--)
    {
        cva = tw[i] & dif;
        if(cva > 0)
        {
            su += par[i][r].dis;
            r = par[i][r].to;
        }
    }
    if(l == r)
    {
        bdi = su;
        return l;
    }
    for(i=ru-1; i>=0; i--)
    {
        if(par[i][l].to != par[i][r].to)
        {
            su += par[i][l].dis + par[i][r].dis;
            l = par[i][l].to;
            r = par[i][r].to;
        }
    }
    su += par[0][l].dis + par[0][r].dis;
    l = par[0][l].to;
    bdi = su;
    return l;
}
int main()
{
    int i,j,n,m,f,t,cdi,cn,fn,of = 0,tn,q,k,o,mhi,mno,cva,chi,cind,su;
    scanf("%d",&n);
    for(i=1; i<n; i++)
    {
        scanf("%d %d %d",&f,&t,&cdi);
        pat[f].push_back({t,cdi});
        pat[t].push_back({f,cdi});
    }
    re(0,-1,0);
    par[0][0] = {-1,-1};
    ru = 1;
    tw[0] = 1;
    while(of == 0)
    {
        of = 1;
        tw[ru] = tw[ru-1] * 2;
        for(i=0; i<n; i++)
        {
            tn = par[ru-1][i].to;
            if(tn != -1)
            {
                par[ru][i].to = par[ru-1][tn].to;
                if(par[ru][i].to != -1)
                {
                    par[ru][i].dis = par[ru-1][tn].dis + par[ru-1][i].dis;
                }
                else
                {
                    par[ru][i].dis = -1;
                }
                of = 0;
            }
            else
            {
                par[ru][i] = {-1,-1};
            }
        }
        ru ++;
    }
    scanf("%d",&q);
    for(i=0; i<q; i++)
    {
        su = 0;
        for(j=0; j<5; j++)
        {
            scanf("%d",&cus[j]);
            if(j == 0)
            {
                mhi = hii[cus[0]];
                mno = cus[0];
                continue;
            }
            chi = -1;
            for(k=j-1; k>=0; k--)
            {
                cn = lca(cus[j],cus[k]);
                cva = bdi;
                if(hii[cn] > chi)
                {
                    chi = hii[cn];
                    fn = cn;
                    cind = k;
                }
            }
            if(chi < mhi)
            {
                mno = lca(mno,cus[j]);
                su += bdi;
                mhi = hii[mno];
            }
            else
            {
                lca(fn,cus[j]);
                su += bdi;
            }
        }
        printf("%d\n",su);
    }
    return 0;
}

Compilation message (stderr)

roadsideadverts.cpp: In function 'int re(int, int, int)':
roadsideadverts.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<we>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(i=0; i<pat[cn].size(); i++)
      |              ~^~~~~~~~~~~~~~~
roadsideadverts.cpp: In function 'int lca(int, int)':
roadsideadverts.cpp:32:17: warning: unused variable 'j' [-Wunused-variable]
   32 |     int f,dif,i,j,cva,su = 0;
      |                 ^
roadsideadverts.cpp: In function 'int main()':
roadsideadverts.cpp:70:15: warning: unused variable 'm' [-Wunused-variable]
   70 |     int i,j,n,m,f,t,cdi,cn,fn,of = 0,tn,q,k,o,mhi,mno,cva,chi,cind,su;
      |               ^
roadsideadverts.cpp:70:45: warning: unused variable 'o' [-Wunused-variable]
   70 |     int i,j,n,m,f,t,cdi,cn,fn,of = 0,tn,q,k,o,mhi,mno,cva,chi,cind,su;
      |                                             ^
roadsideadverts.cpp:70:55: warning: variable 'cva' set but not used [-Wunused-but-set-variable]
   70 |     int i,j,n,m,f,t,cdi,cn,fn,of = 0,tn,q,k,o,mhi,mno,cva,chi,cind,su;
      |                                                       ^~~
roadsideadverts.cpp:70:63: warning: variable 'cind' set but not used [-Wunused-but-set-variable]
   70 |     int i,j,n,m,f,t,cdi,cn,fn,of = 0,tn,q,k,o,mhi,mno,cva,chi,cind,su;
      |                                                               ^~~~
roadsideadverts.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
roadsideadverts.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         scanf("%d %d %d",&f,&t,&cdi);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
roadsideadverts.cpp:115:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |             scanf("%d",&cus[j]);
      |             ~~~~~^~~~~~~~~~~~~~
roadsideadverts.cpp:136:26: warning: 'mno' may be used uninitialized in this function [-Wmaybe-uninitialized]
  136 |                 mno = lca(mno,cus[j]);
      |                       ~~~^~~~~~~~~~~~
roadsideadverts.cpp:134:13: warning: 'mhi' may be used uninitialized in this function [-Wmaybe-uninitialized]
  134 |             if(chi < mhi)
      |             ^~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30