oj.uz

Submission #376232

# Submission time Handle Problem Language Result Execution time Memory
376232 2021-03-11T05:24:05 Z daniel920712 Designated Cities (JOI19_designated_cities) C++14
22 / 100
 1238 ms 95296 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: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:151:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  151 |         scanf("%lld",&M);
      |         ~~~~~^~~~~~~~~~~
designated_cities.cpp:154:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  154 |             scanf("%lld",&a);
      |             ~~~~~^~~~~~~~~~~
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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 208 ms 23788 KB Output is correct
3 Correct 178 ms 23788 KB Output is correct
4 Correct 193 ms 23872 KB Output is correct
5 Correct 190 ms 23788 KB Output is correct
6 Correct 191 ms 23788 KB Output is correct
7 Correct 190 ms 23788 KB Output is correct
8 Correct 196 ms 23916 KB Output is correct
9 Correct 209 ms 23872 KB Output is correct
10 Correct 177 ms 23916 KB Output is correct
11 Correct 203 ms 23872 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 487 ms 62444 KB Output is correct
3 Correct 501 ms 85196 KB Output is correct
4 Correct 460 ms 62188 KB Output is correct
5 Correct 494 ms 62432 KB Output is correct
6 Correct 467 ms 65516 KB Output is correct
7 Correct 569 ms 61660 KB Output is correct
8 Correct 502 ms 86124 KB Output is correct
9 Correct 633 ms 61372 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 517 ms 65340 KB Output is correct
3 Correct 513 ms 95296 KB Output is correct
4 Correct 495 ms 65388 KB Output is correct
5 Correct 661 ms 65504 KB Output is correct
6 Correct 518 ms 69868 KB Output is correct
7 Correct 1144 ms 64724 KB Output is correct
8 Correct 521 ms 81900 KB Output is correct
9 Correct 1238 ms 64596 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 208 ms 23788 KB Output is correct
3 Correct 178 ms 23788 KB Output is correct
4 Correct 193 ms 23872 KB Output is correct
5 Correct 190 ms 23788 KB Output is correct
6 Correct 191 ms 23788 KB Output is correct
7 Correct 190 ms 23788 KB Output is correct
8 Correct 196 ms 23916 KB Output is correct
9 Correct 209 ms 23872 KB Output is correct
10 Correct 177 ms 23916 KB Output is correct
11 Correct 203 ms 23872 KB Output is correct
12 Correct 16 ms 23788 KB Output is correct
13 Incorrect 18 ms 24172 KB Output isn't correct
14 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 487 ms 62444 KB Output is correct
3 Correct 501 ms 85196 KB Output is correct
4 Correct 460 ms 62188 KB Output is correct
5 Correct 494 ms 62432 KB Output is correct
6 Correct 467 ms 65516 KB Output is correct
7 Correct 569 ms 61660 KB Output is correct
8 Correct 502 ms 86124 KB Output is correct
9 Correct 633 ms 61372 KB Output is correct
10 Correct 16 ms 23788 KB Output is correct
11 Correct 517 ms 65340 KB Output is correct
12 Correct 513 ms 95296 KB Output is correct
13 Correct 495 ms 65388 KB Output is correct
14 Correct 661 ms 65504 KB Output is correct
15 Correct 518 ms 69868 KB Output is correct
16 Correct 1144 ms 64724 KB Output is correct
17 Correct 521 ms 81900 KB Output is correct
18 Correct 1238 ms 64596 KB Output is correct
19 Correct 16 ms 23788 KB Output is correct
20 Incorrect 504 ms 65644 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 208 ms 23788 KB Output is correct
3 Correct 178 ms 23788 KB Output is correct
4 Correct 193 ms 23872 KB Output is correct
5 Correct 190 ms 23788 KB Output is correct
6 Correct 191 ms 23788 KB Output is correct
7 Correct 190 ms 23788 KB Output is correct
8 Correct 196 ms 23916 KB Output is correct
9 Correct 209 ms 23872 KB Output is correct
10 Correct 177 ms 23916 KB Output is correct
11 Correct 203 ms 23872 KB Output is correct
12 Correct 16 ms 23788 KB Output is correct
13 Correct 487 ms 62444 KB Output is correct
14 Correct 501 ms 85196 KB Output is correct
15 Correct 460 ms 62188 KB Output is correct
16 Correct 494 ms 62432 KB Output is correct
17 Correct 467 ms 65516 KB Output is correct
18 Correct 569 ms 61660 KB Output is correct
19 Correct 502 ms 86124 KB Output is correct
20 Correct 633 ms 61372 KB Output is correct
21 Correct 16 ms 23788 KB Output is correct
22 Correct 517 ms 65340 KB Output is correct
23 Correct 513 ms 95296 KB Output is correct
24 Correct 495 ms 65388 KB Output is correct
25 Correct 661 ms 65504 KB Output is correct
26 Correct 518 ms 69868 KB Output is correct
27 Correct 1144 ms 64724 KB Output is correct
28 Correct 521 ms 81900 KB Output is correct
29 Correct 1238 ms 64596 KB Output is correct
30 Correct 16 ms 23788 KB Output is correct
31 Incorrect 18 ms 24172 KB Output isn't correct
32 Halted 0 ms 0 KB -