Submission #1276725

#TimeUsernameProblemLanguageResultExecution timeMemory
1276725TINMuseum (CEOI17_museum)C++17
80 / 100
3123 ms784396 KiB
#include <bits/stdc++.h> #define FNAME "RUNNING" using namespace std; const int N = 1e4 + 1; int n, k, s; vector<pair<int,int>> adj[N]; int sz[N]; int dp[N][N][2]; void Task() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(FNAME".INP","r")) { freopen(FNAME".INP","r",stdin); freopen(FNAME".OUT","w",stdout); } } void Input() { memset(dp, 0x3f, sizeof(dp)); cin >> n >> k >> s; for (int i = 1; i < n; i++) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } } int limu, limv; void DFS(int u, int par) { dp[u][0][0] = 0; dp[u][1][0] = dp[u][1][1] = 0; sz[u] = 1; for (auto e : adj[u]) { int v, w; tie(v, w) = e; if (v ^ par) { DFS(v, u); sz[u] += sz[v]; limu = min(sz[u], k); for (int x = limu; x >= 2; x--) { limv = min(sz[v], x); for (int y = 1; y <= limv; y++) { dp[u][x][0] = min(dp[u][x][0], dp[u][x - y][0] + dp[v][y][0] + w * 2); dp[u][x][1] = min(dp[u][x][1], dp[u][x - y][0] + w + dp[v][y][1]); dp[u][x][1] = min(dp[u][x][1], dp[u][x - y][1] + dp[v][y][0] + w * 2); } } } } } void solve() { DFS(s, s); cout << min(dp[s][k][0], dp[s][k][1]) << '\n'; } void Solve() { Input(); solve(); } int main() { Task(); Solve(); return 2231^2231; }

Compilation message (stderr)

museum.cpp: In function 'void Task()':
museum.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen(FNAME".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen(FNAME".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...