oj.uz

Submission #376231

# Submission time Handle Problem Language Result Execution time Memory
376231 2021-03-11T05:23:40 Z daniel920712 Designated Cities (JOI19_designated_cities) C++14
16 / 100
 1246 ms 96032 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <set>

using namespace std;
vector < pair < long long , long long > > Next[200005];
map < long long , long long > all[200005];
set < long long > vis[200005];
long long ans[200005];
long long xx[200005];
long long DP[5][200005];
void F(long long here,long long fa)
{
    for(auto i:Next[here])
    {
        if(i.first!=fa)
        {
            ans[1]+=i.second;
            F(i.first,here);
        }
    }
}
void F2(long long here,long long fa)
{
    for(auto i:Next[here])
    {
        if(i.first!=fa)
        {
            ans[i.first]=ans[here]-all[here][i.first]+all[i.first][here];
            F2(i.first,here);
        }
    }
}
void F3(long long here,long long fa)
{
    for(auto i:Next[here])
    {
        if(i.first!=fa)
        {
            vis[here].insert(i.first);
            F3(i.first,here);
        }
    }
}
void F4(long long here,long long fa)
{
    long long x=1e18,y=0,z,tt;
    for(auto i:Next[here]) if(i.first!=fa) F4(i.first,here);
    DP[0][here]=0;
    DP[1][here]=1e18;
    DP[2][here]=1e18;

    for(auto i:Next[here])
    {
        if(i.first!=fa)
        {
            DP[0][here]+=DP[0][i.first];
            DP[0][here]+=all[here][i.first];
        }
    }
    DP[1][here]=DP[0][here];
    x=1e18;
    y=0;
    for(auto i:Next[here])
    {
        if(i.first!=fa)
        {
            x=min(x,0-DP[0][i.first]-all[here][i.first]+DP[1][i.first]);
            y+=DP[0][i.first]+all[here][i.first];
        }
    }

    DP[2][here]=DP[0][here]+x;
    DP[1][here]=min(DP[1][here],y+x);
    x=1e18;
    y=0;
    for(auto i:Next[here])
    {
        if(i.first!=fa)
        {
            x=min(x,0-DP[0][i.first]-all[here][i.first]+DP[2][i.first]+all[i.first][here]);
            y+=DP[0][i.first]+all[here][i.first];
        }
    }
    DP[2][here]=min(DP[2][here],y+x);

    x=1e18;
    y=0;
    z=1e18;

    for(auto i:Next[here])
    {
        if(i.first!=fa)
        {
            tt=0-DP[0][i.first]-all[here][i.first]+DP[1][i.first];
            if(tt<x)
            {
                z=x;
                x=tt;
            }
            else if(tt<z)
            {
                z=tt;
            }

            y+=DP[0][i.first]+all[here][i.first];
        }
    }
    DP[2][here]=min(DP[2][here],y+x+z);
    //printf("%lld %lld %lld %lld\n",here,DP[0][here],DP[1][here],DP[2][here]);
    //for(auto i:Next[here]) if(i.first!=fa) x=min(x,0-DP[0][i.first]-all[here][i.first]+DP[1][i.first]);


}
int main()
{
    long long N,M,i,j,k,a,b,c,d,how=1e18;
    scanf("%lld",&N);

    for(i=1;i<N;i++)
    {

        scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
        Next[a].push_back(make_pair(b,c));
        Next[b].push_back(make_pair(a,d));
        all[a][b]=c;
        all[b][a]=d;
    }
    for(i=1;i<=N;i++) xx[i]=1e18;
    /*if(N<=16)
    {
        for(i=0;i<(1<<N);i++)
        {
            a=0;
            b=0;
            for(j=1;j<=N;j++) vis[j].clear();
            for(j=0;j<N;j++)
            {
                if(i&(1<<j))
                {
                    F3(j+1,-1);
                    a++;
                }
            }
            for(j=1;j<=N;j++) for(auto k:Next[j]) if(vis[j].find(k.first)==vis[j].end()) b+=all[k.first][j];
            xx[a]=min(xx[a],b);
        }
        scanf("%lld",&M);
        while(M--)
        {
            scanf("%lld",&a);
            printf("%lld\n",xx[a]);
        }
    }
    else*/
    {
        scanf("%lld %lld",&a,&b);

        if(b==1)
        {
            F(1,-1);
            F2(1,-1);
            for(i=1;i<=N;i++)
            {
                how=min(how,ans[i]);
            }
            printf("%lld\n",how);
        }
        else
        {
            F4(1,-1);
            printf("%lld\n",DP[2][1]);
        }

    }

    return 0;
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:120:17: warning: unused variable 'M' [-Wunused-variable]
  120 |     long long N,M,i,j,k,a,b,c,d,how=1e18;
      |                 ^
designated_cities.cpp:120:21: warning: unused variable 'j' [-Wunused-variable]
  120 |     long long N,M,i,j,k,a,b,c,d,how=1e18;
      |                     ^
designated_cities.cpp:120:23: warning: unused variable 'k' [-Wunused-variable]
  120 |     long long N,M,i,j,k,a,b,c,d,how=1e18;
      |                       ^
designated_cities.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  121 |     scanf("%lld",&N);
      |     ~~~~~^~~~~~~~~~~
designated_cities.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  126 |         scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:160:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  160 |         scanf("%lld %lld",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 481 ms 62572 KB Output is correct
3 Correct 495 ms 85228 KB Output is correct
4 Correct 467 ms 62140 KB Output is correct
5 Correct 502 ms 62336 KB Output is correct
6 Correct 467 ms 65516 KB Output is correct
7 Correct 581 ms 61744 KB Output is correct
8 Correct 495 ms 85996 KB Output is correct
9 Correct 651 ms 61396 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 511 ms 65508 KB Output is correct
3 Correct 516 ms 96032 KB Output is correct
4 Correct 504 ms 66284 KB Output is correct
5 Correct 601 ms 66400 KB Output is correct
6 Correct 521 ms 70508 KB Output is correct
7 Correct 1171 ms 65364 KB Output is correct
8 Correct 530 ms 82796 KB Output is correct
9 Correct 1246 ms 65600 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 481 ms 62572 KB Output is correct
3 Correct 495 ms 85228 KB Output is correct
4 Correct 467 ms 62140 KB Output is correct
5 Correct 502 ms 62336 KB Output is correct
6 Correct 467 ms 65516 KB Output is correct
7 Correct 581 ms 61744 KB Output is correct
8 Correct 495 ms 85996 KB Output is correct
9 Correct 651 ms 61396 KB Output is correct
10 Correct 16 ms 23788 KB Output is correct
11 Correct 511 ms 65508 KB Output is correct
12 Correct 516 ms 96032 KB Output is correct
13 Correct 504 ms 66284 KB Output is correct
14 Correct 601 ms 66400 KB Output is correct
15 Correct 521 ms 70508 KB Output is correct
16 Correct 1171 ms 65364 KB Output is correct
17 Correct 530 ms 82796 KB Output is correct
18 Correct 1246 ms 65600 KB Output is correct
19 Correct 15 ms 23788 KB Output is correct
20 Incorrect 531 ms 66796 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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