oj.uz

Submission #338255

# Submission time Handle Problem Language Result Execution time Memory
338255 2020-12-22T20:06:04 Z ScarletS Museum (CEOI17_museum) C++17
100 / 100
 693 ms 784620 KB 
#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[2][mn][mn],sub[mn],k;
vector<pii> edges[mn];
//dp[0/1][i][j]
//i - parent vertice
//j - number of vertices visited
//0 -> return to i
//1 -> no return to i

void dfs(int c, int p)
{
    sub[c]=1;
    dp[0][c][1]=0;
    dp[1][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=max(sub[i.f]+j-sub[c],1);K<=min(sub[i.f],j);++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],min(dp[0][c][j-K]+dp[1][i.f][K]+i.s,dp[1][c][j-K]+dp[0][i.f][K]+2*i.s));
                }
        }
}

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=0;i<=n;++i)
        for (int j=0;j<=k;++j)
        {
            dp[0][i][j]=INF;
            dp[1][i][j]=INF;
        }
    dfs(x,0);
    cout<<dp[1][x][k];
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 91500 KB Output is correct
2 Correct 180 ms 91884 KB Output is correct
3 Correct 438 ms 221008 KB Output is correct
4 Correct 246 ms 131328 KB Output is correct
5 Correct 195 ms 99436 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 91500 KB Output is correct
2 Correct 180 ms 91884 KB Output is correct
3 Correct 438 ms 221008 KB Output is correct
4 Correct 246 ms 131328 KB Output is correct
5 Correct 195 ms 99436 KB Output is correct
6 Correct 189 ms 91116 KB Output is correct
7 Correct 311 ms 166512 KB Output is correct
8 Correct 353 ms 90604 KB Output is correct
9 Correct 308 ms 90860 KB Output is correct
10 Correct 194 ms 91244 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 178 ms 91500 KB Output is correct
7 Correct 180 ms 91884 KB Output is correct
8 Correct 438 ms 221008 KB Output is correct
9 Correct 246 ms 131328 KB Output is correct
10 Correct 195 ms 99436 KB Output is correct
11 Correct 189 ms 91116 KB Output is correct
12 Correct 311 ms 166512 KB Output is correct
13 Correct 353 ms 90604 KB Output is correct
14 Correct 308 ms 90860 KB Output is correct
15 Correct 194 ms 91244 KB Output is correct
16 Correct 226 ms 162156 KB Output is correct
17 Correct 389 ms 473836 KB Output is correct
18 Correct 293 ms 199148 KB Output is correct
19 Correct 342 ms 161156 KB Output is correct
20 Correct 227 ms 161516 KB Output is correct
21 Correct 632 ms 784492 KB Output is correct
22 Correct 556 ms 784108 KB Output is correct
23 Correct 678 ms 784364 KB Output is correct
24 Correct 628 ms 784112 KB Output is correct
25 Correct 693 ms 784620 KB Output is correct