답안 #376228

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
376228 2021-03-11T05:16:46 Z daniel920712 Designated Cities (JOI19_designated_cities) C++14
13 / 100
634 ms 87288 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]=1e18;
    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];
    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[here][i.first]);
            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[2][i.first]+all[here][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);
    //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:118:23: warning: unused variable 'k' [-Wunused-variable]
  118 |     long long N,M,i,j,k,a,b,c,d,how=1e18;
      |                       ^
designated_cities.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  119 |     scanf("%lld",&N);
      |     ~~~~~^~~~~~~~~~~
designated_cities.cpp:124:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  124 |         scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:149:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  149 |         scanf("%lld",&M);
      |         ~~~~~^~~~~~~~~~~
designated_cities.cpp:152:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  152 |             scanf("%lld",&a);
      |             ~~~~~^~~~~~~~~~~
designated_cities.cpp:158:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  158 |         scanf("%lld %lld",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 197 ms 23916 KB Output is correct
3 Correct 184 ms 23916 KB Output is correct
4 Correct 194 ms 23788 KB Output is correct
5 Correct 186 ms 23916 KB Output is correct
6 Correct 189 ms 23788 KB Output is correct
7 Correct 183 ms 23788 KB Output is correct
8 Correct 202 ms 23788 KB Output is correct
9 Correct 205 ms 23872 KB Output is correct
10 Correct 182 ms 23916 KB Output is correct
11 Correct 207 ms 23872 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 466 ms 62248 KB Output is correct
3 Correct 496 ms 86508 KB Output is correct
4 Correct 473 ms 63604 KB Output is correct
5 Correct 489 ms 63456 KB Output is correct
6 Correct 481 ms 66844 KB Output is correct
7 Correct 558 ms 63104 KB Output is correct
8 Correct 505 ms 87288 KB Output is correct
9 Correct 634 ms 62804 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23916 KB Output is correct
2 Incorrect 508 ms 65680 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 197 ms 23916 KB Output is correct
3 Correct 184 ms 23916 KB Output is correct
4 Correct 194 ms 23788 KB Output is correct
5 Correct 186 ms 23916 KB Output is correct
6 Correct 189 ms 23788 KB Output is correct
7 Correct 183 ms 23788 KB Output is correct
8 Correct 202 ms 23788 KB Output is correct
9 Correct 205 ms 23872 KB Output is correct
10 Correct 182 ms 23916 KB Output is correct
11 Correct 207 ms 23872 KB Output is correct
12 Correct 19 ms 23788 KB Output is correct
13 Incorrect 17 ms 24172 KB Output isn't correct
14 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 466 ms 62248 KB Output is correct
3 Correct 496 ms 86508 KB Output is correct
4 Correct 473 ms 63604 KB Output is correct
5 Correct 489 ms 63456 KB Output is correct
6 Correct 481 ms 66844 KB Output is correct
7 Correct 558 ms 63104 KB Output is correct
8 Correct 505 ms 87288 KB Output is correct
9 Correct 634 ms 62804 KB Output is correct
10 Correct 15 ms 23916 KB Output is correct
11 Incorrect 508 ms 65680 KB Output isn't correct
12 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 197 ms 23916 KB Output is correct
3 Correct 184 ms 23916 KB Output is correct
4 Correct 194 ms 23788 KB Output is correct
5 Correct 186 ms 23916 KB Output is correct
6 Correct 189 ms 23788 KB Output is correct
7 Correct 183 ms 23788 KB Output is correct
8 Correct 202 ms 23788 KB Output is correct
9 Correct 205 ms 23872 KB Output is correct
10 Correct 182 ms 23916 KB Output is correct
11 Correct 207 ms 23872 KB Output is correct
12 Correct 16 ms 23788 KB Output is correct
13 Correct 466 ms 62248 KB Output is correct
14 Correct 496 ms 86508 KB Output is correct
15 Correct 473 ms 63604 KB Output is correct
16 Correct 489 ms 63456 KB Output is correct
17 Correct 481 ms 66844 KB Output is correct
18 Correct 558 ms 63104 KB Output is correct
19 Correct 505 ms 87288 KB Output is correct
20 Correct 634 ms 62804 KB Output is correct
21 Correct 15 ms 23916 KB Output is correct
22 Incorrect 508 ms 65680 KB Output isn't correct
23 Halted 0 ms 0 KB -