oj.uz

Submission #1119588

# Submission time Handle Problem Language Result Execution time Memory
1119588 2024-11-27T07:19:40 Z InvMOD Museum (CEOI17_museum) C++14
100 / 100
 412 ms 308176 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define dbg(x) "[" #x " = " << (x) << "]"
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 2e5+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;


void solve()
{
    int n,k,start; cin >> n >> k >> start;

    vector<vector<pair<int,int>>> adj(n+1, vector<pair<int,int>>());
    FOR(i, 1, n-1){
        int u,v,c; cin >> u >> v >> c;
        adj[u].emplace_back(v, c);
        adj[v].emplace_back(u, c);
    }

    vector<int> sz; sz.resize(n+1);
    vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(2, vector<ll>()));

    function<vector<vector<ll>>(vector<vector<ll>>&, vector<vector<ll>>&)> combine = [&](vector<vector<ll>>& dad, vector<vector<ll>>& child){
        vector<vector<ll>> combined(2, vector<ll>(sz(dad[0]) + sz(child[0]) - 1, INF));

        FOR(i, 0, sz(dad[0]) - 1){
            combined[0][i] = dad[0][i];
            combined[1][i] = dad[1][i];
        }

        FOR(i, 1, sz(child[0]) - 1){
            combined[0][i] = min(combined[0][i], child[0][i]);
            combined[1][i] = min(combined[1][i], child[1][i]);
        }

        FOR(i, 1, sz(dad[0]) - 1){
            FOR(j, 1, sz(child[0]) - 1){
                combined[0][i + j] = min(combined[0][i + j], dad[0][i] + child[0][j]);
                combined[1][i + j] = min(combined[1][i + j], dad[0][i] + child[1][j]);
                combined[1][i + j] = min(combined[1][i + j], dad[1][i] + child[0][j]);
            }
        }
        return combined;
    };

    auto dfs = [&](auto&& dfs, int x, int p) -> void{
        dp[x][0] = {(ll)1e12, (ll)0};
        dp[x][1] = {(ll)1e12, (ll)0};

        sz[x] = 1;
        for(pair<int,int> e : adj[x]){
            int v = e.first, w = e.second;
            if(v != p){
                dfs(dfs, v, x);
                FOR(i, 1, sz[v]){
                    dp[v][0][i] = dp[v][0][i] + 2ll * w;
                    dp[v][1][i] = dp[v][1][i] + 1ll * w;
                }

                sz[x] += sz[v];
                dp[x] = combine(dp[x], dp[v]);
            }
        }
    };

    dfs(dfs, start, - 1);
    cout << min(dp[start][1][k], dp[start][0][k]) <<"\n";
    return;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

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

Compilation message

museum.cpp: In function 'int main()':
museum.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
museum.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 6472 KB Output is correct
2 Correct 106 ms 7308 KB Output is correct
3 Correct 367 ms 308176 KB Output is correct
4 Correct 199 ms 97356 KB Output is correct
5 Correct 138 ms 24652 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 6472 KB Output is correct
2 Correct 106 ms 7308 KB Output is correct
3 Correct 367 ms 308176 KB Output is correct
4 Correct 199 ms 97356 KB Output is correct
5 Correct 138 ms 24652 KB Output is correct
6 Correct 124 ms 5048 KB Output is correct
7 Correct 285 ms 179888 KB Output is correct
8 Correct 401 ms 3484 KB Output is correct
9 Correct 282 ms 3736 KB Output is correct
10 Correct 140 ms 5076 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 400 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 101 ms 6472 KB Output is correct
7 Correct 106 ms 7308 KB Output is correct
8 Correct 367 ms 308176 KB Output is correct
9 Correct 199 ms 97356 KB Output is correct
10 Correct 138 ms 24652 KB Output is correct
11 Correct 124 ms 5048 KB Output is correct
12 Correct 285 ms 179888 KB Output is correct
13 Correct 401 ms 3484 KB Output is correct
14 Correct 282 ms 3736 KB Output is correct
15 Correct 140 ms 5076 KB Output is correct
16 Correct 108 ms 7932 KB Output is correct
17 Correct 114 ms 7484 KB Output is correct
18 Correct 236 ms 115268 KB Output is correct
19 Correct 297 ms 3512 KB Output is correct
20 Correct 115 ms 5476 KB Output is correct
21 Correct 287 ms 170396 KB Output is correct
22 Correct 123 ms 6800 KB Output is correct
23 Correct 265 ms 3532 KB Output is correct
24 Correct 125 ms 5124 KB Output is correct
25 Correct 412 ms 298136 KB Output is correct