oj.uz

Submission #658951

# Submission time Handle Problem Language Result Execution time Memory
658951 2022-11-15T14:56:57 Z Soul234 Museum (CEOI17_museum) C++14
100 / 100
 453 ms 784676 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"
#define fi first
#define se second

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
using db = long double;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

tcT> bool ckmin(T&a, const T&b) {
    return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a=b,1 : 0; }

const int MOD = 1e9 + 7;
const ll INF = 1e18;

const int MX = 1e4+2;

int N, K, X;

int dp[2][MX][MX];
int sz[MX];

V<pi> adj[MX];

void dfs(int u, int p) {
    sz[u] = 1;
    F0R(i, 2) dp[i][u][0] = dp[i][u][1] = 0;
    each(ed, adj[u]) if(ed.fi != p) {
        int v = ed.fi, c = ed.se;
        dfs(v, u);
        R0F(i, sz[u]+1) {
            ROF(j,1,sz[v]+1) {
                ckmin(dp[0][u][i+j], dp[0][u][i] + 2*c + dp[0][v][j]);
                ckmin(dp[1][u][i+j], dp[0][u][i] + dp[1][v][j] + c);
                ckmin(dp[1][u][i+j], dp[1][u][i] + 2*c + dp[0][v][j]);
            }
        }
        sz[u] += sz[v];
    }
}

void solve() {
    cin >> N >> K >> X;
    F0R(i, N-1) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].pb({v, c});
        adj[v].pb({u, c});
    }
    memset(dp, 0x3f, sizeof dp);
    dfs(X, -1);
    cout << dp[1][X][K] << nl;
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

museum.cpp: In function 'void setIO(std::string)':
museum.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 783556 KB Output is correct
2 Correct 279 ms 783556 KB Output is correct
3 Correct 280 ms 783564 KB Output is correct
4 Correct 294 ms 783536 KB Output is correct
5 Correct 284 ms 783616 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 784208 KB Output is correct
2 Correct 373 ms 784200 KB Output is correct
3 Correct 441 ms 784616 KB Output is correct
4 Correct 388 ms 784436 KB Output is correct
5 Correct 387 ms 784096 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 784208 KB Output is correct
2 Correct 373 ms 784200 KB Output is correct
3 Correct 441 ms 784616 KB Output is correct
4 Correct 388 ms 784436 KB Output is correct
5 Correct 387 ms 784096 KB Output is correct
6 Correct 376 ms 784252 KB Output is correct
7 Correct 403 ms 784468 KB Output is correct
8 Correct 419 ms 784120 KB Output is correct
9 Correct 452 ms 784204 KB Output is correct
10 Correct 375 ms 784204 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 783556 KB Output is correct
2 Correct 279 ms 783556 KB Output is correct
3 Correct 280 ms 783564 KB Output is correct
4 Correct 294 ms 783536 KB Output is correct
5 Correct 284 ms 783616 KB Output is correct
6 Correct 401 ms 784208 KB Output is correct
7 Correct 373 ms 784200 KB Output is correct
8 Correct 441 ms 784616 KB Output is correct
9 Correct 388 ms 784436 KB Output is correct
10 Correct 387 ms 784096 KB Output is correct
11 Correct 376 ms 784252 KB Output is correct
12 Correct 403 ms 784468 KB Output is correct
13 Correct 419 ms 784120 KB Output is correct
14 Correct 452 ms 784204 KB Output is correct
15 Correct 375 ms 784204 KB Output is correct
16 Correct 382 ms 784220 KB Output is correct
17 Correct 376 ms 784204 KB Output is correct
18 Correct 405 ms 784304 KB Output is correct
19 Correct 409 ms 784196 KB Output is correct
20 Correct 374 ms 784336 KB Output is correct
21 Correct 410 ms 784400 KB Output is correct
22 Correct 403 ms 784204 KB Output is correct
23 Correct 453 ms 784116 KB Output is correct
24 Correct 402 ms 784256 KB Output is correct
25 Correct 423 ms 784676 KB Output is correct