oj.uz

Submission #681216

# Submission time Handle Problem Language Result Execution time Memory
681216 2023-01-12T14:35:29 Z sysia Museum (CEOI17_museum) C++17
100 / 100
 997 ms 707080 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

// #define int long long
typedef pair<int, int> T;
const int oo = 2e9+7;

/*
dp[v][k] = minimalny koszt podrozowania zaczynajac w v (byc moze przechodzac kilka razy przez v do roznych poddrzew) i konczac w v, odwiedzajac k wierzcholkow
dp[v][k] = to samo, tylko konczymy gdziekolwiek w poddrzewie v

zlozonosc: przechodzenie po i, j w dfs jest ograniczone z gory przez ilosc sciezek w drzewie, czyli O(n^2)
:333
*/

void solve(){
    int n, k, st; cin >> n >> k >> st;
    vector<vector<T>>g(n+1);
    for (int i = 1; i<n; i++){
        int a, b, c; cin >> a >> b >> c;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    vector<int>sub(n+1);
    vector<vector<int>>dp(n+1, vector<int>(k+1, oo));
    vector<vector<int>>dp2(n+1, vector<int>(k+1, oo));
    function<void(int, int)>dfs = [&](int v, int pa){
        sub[v] = 1;
        dp[v][0] = 0;
        dp[v][1] = 0;
        dp2[v][0] = 0;
        dp2[v][1] = 0;
        for (auto [x, c]: g[v]){
            if (x == pa) continue;
            dfs(x, v);
            for (int i = sub[v]; i>=0; i--){ 
                for (int j = sub[x]; j>=1; j--){ //musimy odwiedzic co najmniej jeden wierzcholek w poddrzewie x, skoro do niego wchodzimy, co nie?
                    //od tylu, by nie robic overcounting
                    if (i + j > k) continue;
                    dp[v][i+j] =  min(dp[v][i+j],  dp[v][i] +  dp[x][j] + 2 * c); 
                    dp2[v][i+j] = min(dp2[v][i+j], dp[v][i] +  dp2[x][j]+ c);
                    dp2[v][i+j] = min(dp2[v][i+j], dp2[v][i]+  dp[x][j] + 2 * c);
                    //1. wchodzimy do jakichs poddrzew dzieci v, zawracamy i wchodzimy do jakiegos poddrzewa x znowu
                    //2. wchodzimy do jakichs poddrzew dzieci x, wchodzimy do v, pozniej do x i nie wracamy juz z v
                    //3. wchodzimy do x, wracamy i to v z idziemy tyyylko w dol
                    //mmm kocham syf na podzbiorach
                }
            }
            sub[v] += sub[x];
        }
    };
    dfs(st, st);
    cout << dp2[st][k] << "\n";
}

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

    solve();

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 224 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 9672 KB Output is correct
2 Correct 40 ms 9676 KB Output is correct
3 Correct 61 ms 10196 KB Output is correct
4 Correct 51 ms 9960 KB Output is correct
5 Correct 43 ms 9756 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 9672 KB Output is correct
2 Correct 40 ms 9676 KB Output is correct
3 Correct 61 ms 10196 KB Output is correct
4 Correct 51 ms 9960 KB Output is correct
5 Correct 43 ms 9756 KB Output is correct
6 Correct 41 ms 9676 KB Output is correct
7 Correct 57 ms 10120 KB Output is correct
8 Correct 86 ms 9684 KB Output is correct
9 Correct 72 ms 9644 KB Output is correct
10 Correct 49 ms 9776 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 224 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 45 ms 9672 KB Output is correct
7 Correct 40 ms 9676 KB Output is correct
8 Correct 61 ms 10196 KB Output is correct
9 Correct 51 ms 9960 KB Output is correct
10 Correct 43 ms 9756 KB Output is correct
11 Correct 41 ms 9676 KB Output is correct
12 Correct 57 ms 10120 KB Output is correct
13 Correct 86 ms 9684 KB Output is correct
14 Correct 72 ms 9644 KB Output is correct
15 Correct 49 ms 9776 KB Output is correct
16 Correct 159 ms 80088 KB Output is correct
17 Correct 565 ms 393368 KB Output is correct
18 Correct 182 ms 80332 KB Output is correct
19 Correct 184 ms 80172 KB Output is correct
20 Correct 158 ms 80224 KB Output is correct
21 Correct 904 ms 706812 KB Output is correct
22 Correct 869 ms 706528 KB Output is correct
23 Correct 819 ms 706616 KB Output is correct
24 Correct 796 ms 706612 KB Output is correct
25 Correct 997 ms 707080 KB Output is correct