Submission #336810

#	Time	Username	Problem	Language	Result	Execution time	Memory
336810		ScarletS	Museum (CEOI17_museum)	C++17	0 / 100	8 ms	1900 KiB

museum

#include <bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;

const int mn = 1e4+1, INF=1e9;
int dp[0][mn][mn],sub[mn],k;
vector<pii> edges[mn];

void dfs(int c, int p)
{
    sub[c]=1;
    dp[0][c][1]=0;
    for (pii i : edges[c])
        if (i.f!=p)
        {
            dfs(i.f,c);
            sub[c]+=sub[i.f];
            for (int j=sub[c];j>1;++j)
                for (int K=1;K<=sub[i.f];++K)
                {
                    dp[0][c][j]=min(dp[0][c][j],dp[0][c][j-K]+dp[0][i.f][K]+2*i.s);
                    dp[1][c][j]=min(dp[1][c][j],dp[0][c][j-K]+dp[1][i.f][K]);
                }
        }
    //cout<<c<<" "<<sub[c]<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,x,a,b,c;
    cin>>n>>k>>x;
    for (int i=1;i<n;++i)
    {
        cin>>a>>b>>c;
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    for (int i=1;i<=n;++i)
        for (int j=1;j<=k;++j)
        {
            dp[0][i][j]=INF;
            dp[1][i][j]=INF;
        }
    dfs(x,0);
    cout<<dp[1][x][k];
    return 0;
}

Compilation message (stderr)

museum.cpp: In function 'void dfs(int, int)':
museum.cpp:14:9: warning: array subscript 0 is above array bounds of 'int [0][10001][10001]' [-Warray-bounds]
   14 |     dp[0][c][1]=0;
      |     ~~~~^
museum.cpp:8:5: note: while referencing 'dp'
    8 | int dp[0][mn][mn],sub[mn],k;
      |     ^~
museum.cpp:23:53: warning: array subscript 0 is above array bounds of 'int [0][10001][10001]' [-Warray-bounds]
   23 |                     dp[0][c][j]=min(dp[0][c][j],dp[0][c][j-K]+dp[0][i.f][K]+2*i.s);
      |                                                 ~~~~^
museum.cpp:8:5: note: while referencing 'dp'
    8 | int dp[0][mn][mn],sub[mn],k;
      |     ^~
museum.cpp:23:67: warning: array subscript 0 is above array bounds of 'int [0][10001][10001]' [-Warray-bounds]
   23 |                     dp[0][c][j]=min(dp[0][c][j],dp[0][c][j-K]+dp[0][i.f][K]+2*i.s);
      |                                                               ~~~~^
museum.cpp:8:5: note: while referencing 'dp'
    8 | int dp[0][mn][mn],sub[mn],k;
      |     ^~
museum.cpp:23:47: warning: array subscript 0 is above array bounds of 'int [0][10001][10001]' [-Warray-bounds]
   23 |                     dp[0][c][j]=min(dp[0][c][j],dp[0][c][j-K]+dp[0][i.f][K]+2*i.s);
      |                                     ~~~~~~~~~~^
museum.cpp:8:5: note: while referencing 'dp'
    8 | int dp[0][mn][mn],sub[mn],k;
      |     ^~
museum.cpp:23:41: warning: array subscript 0 is above array bounds of 'int [0][10001][10001]' [-Warray-bounds]
   23 |                     dp[0][c][j]=min(dp[0][c][j],dp[0][c][j-K]+dp[0][i.f][K]+2*i.s);
      |                                     ~~~~^
museum.cpp:23:25: warning: array subscript 0 is above array bounds of 'int [0][10001][10001]' [-Warray-bounds]
   23 |                     dp[0][c][j]=min(dp[0][c][j],dp[0][c][j-K]+dp[0][i.f][K]+2*i.s);
      |                     ~~~~^
museum.cpp:8:5: note: while referencing 'dp'
    8 | int dp[0][mn][mn],sub[mn],k;
      |     ^~
museum.cpp:24:53: warning: array subscript 0 is above array bounds of 'int [0][10001][10001]' [-Warray-bounds]
   24 |                     dp[1][c][j]=min(dp[1][c][j],dp[0][c][j-K]+dp[1][i.f][K]);
      |                                                 ~~~~^
museum.cpp:8:5: note: while referencing 'dp'
    8 | int dp[0][mn][mn],sub[mn],k;
      |     ^~
museum.cpp:24:67: warning: array subscript 0 is above array bounds of 'int [0][10001][10001]' [-Warray-bounds]
   24 |                     dp[1][c][j]=min(dp[1][c][j],dp[0][c][j-K]+dp[1][i.f][K]);
      |                                                               ~~~~^
museum.cpp:8:5: note: while referencing 'dp'
    8 | int dp[0][mn][mn],sub[mn],k;
      |     ^~
museum.cpp:24:47: warning: array subscript 0 is above array bounds of 'int [0][10001][10001]' [-Warray-bounds]
   24 |                     dp[1][c][j]=min(dp[1][c][j],dp[0][c][j-K]+dp[1][i.f][K]);
      |                                     ~~~~~~~~~~^
museum.cpp:24:47: warning: array subscript 1 is above array bounds of 'int [0][10001][10001]' [-Warray-bounds]
museum.cpp:8:5: note: while referencing 'dp'
    8 | int dp[0][mn][mn],sub[mn],k;
      |     ^~
museum.cpp:24:41: warning: array subscript 0 is above array bounds of 'int [0][10001][10001]' [-Warray-bounds]
   24 |                     dp[1][c][j]=min(dp[1][c][j],dp[0][c][j-K]+dp[1][i.f][K]);
      |                                     ~~~~^
museum.cpp:24:25: warning: array subscript 0 is above array bounds of 'int [0][10001][10001]' [-Warray-bounds]
   24 |                     dp[1][c][j]=min(dp[1][c][j],dp[0][c][j-K]+dp[1][i.f][K]);
      |                     ~~~~^
museum.cpp:8:5: note: while referencing 'dp'
    8 | int dp[0][mn][mn],sub[mn],k;
      |     ^~
museum.cpp: In function 'int main()':
museum.cpp:44:17: warning: array subscript 0 is above array bounds of 'int [0][10001][10001]' [-Warray-bounds]
   44 |             dp[0][i][j]=INF;
      |             ~~~~^
museum.cpp:8:5: note: while referencing 'dp'
    8 | int dp[0][mn][mn],sub[mn],k;
      |     ^~
museum.cpp:45:17: warning: array subscript 0 is above array bounds of 'int [0][10001][10001]' [-Warray-bounds]
   45 |             dp[1][i][j]=INF;
      |             ~~~~^
museum.cpp:8:5: note: while referencing 'dp'
    8 | int dp[0][mn][mn],sub[mn],k;
      |     ^~
museum.cpp:48:15: warning: array subscript 0 is above array bounds of 'int [0][10001][10001]' [-Warray-bounds]
   48 |     cout<<dp[1][x][k];
      |           ~~~~^
museum.cpp:8:5: note: while referencing 'dp'
    8 | int dp[0][mn][mn],sub[mn],k;
      |     ^~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20