oj.uz

Submission #444901

# Submission time Handle Problem Language Result Execution time Memory
444901 2021-07-15T19:55:54 Z ivan_tudor Museum (CEOI17_museum) C++14
100 / 100
 920 ms 785092 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 10005;
struct Edges{
  int x, c;
};
vector<Edges> gr[N];
int sz[N];
void dfs_prec(int nod, int dad){
  sz[nod] = 1;
  for(auto x:gr[nod])
  if(x.x!=dad){
    dfs_prec(x.x, nod);
    sz[nod] += sz[x.x];
  }
}
int dp[2][N][N];
void joindp(int dp1[], int sz1, int dp2[], int sz2, int dpans[], int val){
  for(int i = sz1; i >=0; i--){
    for(int j = sz2; j>=0; j--){
      dpans[i + j] = min(dpans[i + j], dp1[i] + dp2[j] + val);
    }
  }
}
void dfs(int nod, int dad){
  for(auto x:gr[nod]){
    if(x.x != dad){
      dfs(x.x, nod);
    }
  }
  dp[0][nod][0] = 0;
  dp[1][nod][0] = 0;
  dp[0][nod][1] = 0;
  dp[1][nod][1] = 0;
  int cursz = 1;
  for(auto x:gr[nod]){
    if(x.x == dad)
      continue;
    joindp(dp[1][nod], cursz, dp[0][x.x], sz[x.x], dp[1][nod], 2*x.c);
    joindp(dp[0][nod], cursz, dp[1][x.x], sz[x.x], dp[1][nod], x.c);
    joindp(dp[0][nod], cursz, dp[0][x.x], sz[x.x], dp[0][nod], 2*x.c);
    cursz+=sz[x.x];
  }

}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  for(int i = 0; i < 2; i++){
    for(int j = 0; j < N; j++){
      for(int k = 0; k < N; k++){
        dp[i][j][k] = INT_MAX;
      }
    }
  }
  int n, k, x;
  cin>>n>>k>>x;
  for(int i =1; i < n; i++){
    int a, b, c;
    cin>>a>>b>>c;
    gr[a].push_back({b, c});
    gr[b].push_back({a, c});
  }
  dfs_prec(x, 0);
  dfs(x, 0);
  cout<<dp[1][x][k];
  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 784116 KB Output is correct
2 Correct 438 ms 784252 KB Output is correct
3 Correct 429 ms 784068 KB Output is correct
4 Correct 428 ms 784068 KB Output is correct
5 Correct 429 ms 784068 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 784624 KB Output is correct
2 Correct 601 ms 784836 KB Output is correct
3 Correct 691 ms 784968 KB Output is correct
4 Correct 633 ms 784708 KB Output is correct
5 Correct 606 ms 784688 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 784624 KB Output is correct
2 Correct 601 ms 784836 KB Output is correct
3 Correct 691 ms 784968 KB Output is correct
4 Correct 633 ms 784708 KB Output is correct
5 Correct 606 ms 784688 KB Output is correct
6 Correct 600 ms 784532 KB Output is correct
7 Correct 654 ms 785008 KB Output is correct
8 Correct 920 ms 784620 KB Output is correct
9 Correct 797 ms 784580 KB Output is correct
10 Correct 627 ms 784720 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 784116 KB Output is correct
2 Correct 438 ms 784252 KB Output is correct
3 Correct 429 ms 784068 KB Output is correct
4 Correct 428 ms 784068 KB Output is correct
5 Correct 429 ms 784068 KB Output is correct
6 Correct 601 ms 784624 KB Output is correct
7 Correct 601 ms 784836 KB Output is correct
8 Correct 691 ms 784968 KB Output is correct
9 Correct 633 ms 784708 KB Output is correct
10 Correct 606 ms 784688 KB Output is correct
11 Correct 600 ms 784532 KB Output is correct
12 Correct 654 ms 785008 KB Output is correct
13 Correct 920 ms 784620 KB Output is correct
14 Correct 797 ms 784580 KB Output is correct
15 Correct 627 ms 784720 KB Output is correct
16 Correct 599 ms 784572 KB Output is correct
17 Correct 603 ms 784808 KB Output is correct
18 Correct 637 ms 784860 KB Output is correct
19 Correct 833 ms 784708 KB Output is correct
20 Correct 601 ms 784836 KB Output is correct
21 Correct 653 ms 784896 KB Output is correct
22 Correct 603 ms 784680 KB Output is correct
23 Correct 831 ms 784632 KB Output is correct
24 Correct 609 ms 784708 KB Output is correct
25 Correct 689 ms 785092 KB Output is correct