oj.uz

Submission #423374

# Submission time Handle Problem Language Result Execution time Memory
423374 2021-06-11T03:56:29 Z Amylopectin Roadside Advertisements (NOI17_roadsideadverts) C++14
100 / 100
 116 ms 15784 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 13896 KB Output is correct
2 Correct 100 ms 15704 KB Output is correct
3 Correct 86 ms 15668 KB Output is correct
4 Correct 85 ms 15784 KB Output is correct
5 Correct 87 ms 15768 KB Output is correct
6 Correct 88 ms 15744 KB Output is correct
7 Correct 75 ms 15760 KB Output is correct
8 Correct 76 ms 15744 KB Output is correct
9 Correct 83 ms 15692 KB Output is correct
10 Correct 82 ms 15712 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8388 KB Output is correct
2 Correct 39 ms 14968 KB Output is correct
3 Correct 37 ms 14884 KB Output is correct
4 Correct 37 ms 14832 KB Output is correct
5 Correct 40 ms 14916 KB Output is correct
6 Correct 36 ms 14864 KB Output is correct
7 Correct 44 ms 14840 KB Output is correct
8 Correct 40 ms 15032 KB Output is correct
9 Correct 38 ms 14864 KB Output is correct
10 Correct 49 ms 14892 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 116 ms 13896 KB Output is correct
3 Correct 100 ms 15704 KB Output is correct
4 Correct 86 ms 15668 KB Output is correct
5 Correct 85 ms 15784 KB Output is correct
6 Correct 87 ms 15768 KB Output is correct
7 Correct 88 ms 15744 KB Output is correct
8 Correct 75 ms 15760 KB Output is correct
9 Correct 76 ms 15744 KB Output is correct
10 Correct 83 ms 15692 KB Output is correct
11 Correct 82 ms 15712 KB Output is correct
12 Correct 30 ms 8388 KB Output is correct
13 Correct 39 ms 14968 KB Output is correct
14 Correct 37 ms 14884 KB Output is correct
15 Correct 37 ms 14832 KB Output is correct
16 Correct 40 ms 14916 KB Output is correct
17 Correct 36 ms 14864 KB Output is correct
18 Correct 44 ms 14840 KB Output is correct
19 Correct 40 ms 15032 KB Output is correct
20 Correct 38 ms 14864 KB Output is correct
21 Correct 49 ms 14892 KB Output is correct
22 Correct 112 ms 13796 KB Output is correct
23 Correct 49 ms 8504 KB Output is correct
24 Correct 99 ms 15232 KB Output is correct
25 Correct 76 ms 15300 KB Output is correct
26 Correct 76 ms 15284 KB Output is correct
27 Correct 78 ms 15252 KB Output is correct
28 Correct 74 ms 15300 KB Output is correct
29 Correct 90 ms 15296 KB Output is correct
30 Correct 87 ms 15260 KB Output is correct
31 Correct 78 ms 15208 KB Output is correct