oj.uz

Submission #869001

# Submission time Handle Problem Language Result Execution time Memory
869001 2023-11-02T21:17:44 Z TB_ Museum (CEOI17_museum) C++17
100 / 100
 360 ms 3204 KB 
#include <bits/stdc++.h>
using namespace std;

// #undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")

// #pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
// #pragma GCC target("movbe")                                      // byte swap
// #pragma GCC target("aes,pclmul,rdrnd")                           // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// template<class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define INF (ll)1e9+7
#define fo(i, n) for(ll i=0;i<((ll)n);i++)
#define deb(x) cout << #x << " = " << (x) << endl;
#define deb2(x, y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LSOne(S) ((S) & (-S))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
inline int readint(){ int v = 0; char c; while((c = getchar()) != EOF && c != ' ' && c != '\n'){ v *= 10; v += c - '0'; } return v; }
inline int readintsigned() { int v = 0; int sign = 1; char c = getchar(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } return v * sign; }
inline string readstring() { string s; char c; while ((c = getchar()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } return s; }
template <class result_t=std::chrono::milliseconds,class clock_t=std::chrono::steady_clock,class duration_t = std::chrono::milliseconds>
auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);}
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpii> vvpii;
typedef vector<vpl> vvpl;

vvpl adj(10001);


vvl dp(int u, int last = -1){
    vvl ans = {{0, 0}, {0, 0}};
    for(auto &[v, w] : adj[u]){
        if(v == last) continue;
        vvl res = dp(v, u);
        vl next(ans[0].size()+res[0].size(), INF);
        vl next2(max(ans[0].size()+res[1].size(), ans[1].size()+res[0].size()), INF);
        fo(i, ans[0].size()){
            fo(j, res[0].size()){
                next[i+j] = min(next[i+j], ans[0][i]+res[0][j]+(j?w*2:0));
            }
            fo(j, res[1].size()){
                next2[i+j] = min(next2[i+j], ans[0][i]+res[1][j]+(j?w:0));
            }
        }
        fo(i, ans[1].size()){
            fo(j, res[0].size()){
                next2[i+j] = min(next2[i+j], ans[1][i]+res[0][j]+(j?w*2:0));
            }
        }
        while(next[next.size()-1] == INF) next.pop_back(); 
        while(next2[next2.size()-1] == INF) next2.pop_back(); 
        swap(next, ans[0]);
        swap(next2, ans[1]);
    }
    return ans;
}

int main() {
    // cout << fixed << setprecision(20);
    // auto start = std::chrono::steady_clock::now(); // since(start).count()
    cin.tie(0)->sync_with_stdio(0);

    int n, k, x, a, b, c;
    cin >> n >> k >> x;
    fo(i, n-1){
        cin >> a >> b >> c;
        adj[--a].pb({--b, c});
        adj[b].pb({a, c});
    }
    cout << dp(x-1)[1][k];

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 0 ms 604 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 1876 KB Output is correct
2 Correct 160 ms 1920 KB Output is correct
3 Correct 224 ms 3204 KB Output is correct
4 Correct 188 ms 2348 KB Output is correct
5 Correct 149 ms 2032 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 1876 KB Output is correct
2 Correct 160 ms 1920 KB Output is correct
3 Correct 224 ms 3204 KB Output is correct
4 Correct 188 ms 2348 KB Output is correct
5 Correct 149 ms 2032 KB Output is correct
6 Correct 147 ms 1848 KB Output is correct
7 Correct 208 ms 2840 KB Output is correct
8 Correct 360 ms 1940 KB Output is correct
9 Correct 316 ms 2112 KB Output is correct
10 Correct 163 ms 2084 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 144 ms 1876 KB Output is correct
7 Correct 160 ms 1920 KB Output is correct
8 Correct 224 ms 3204 KB Output is correct
9 Correct 188 ms 2348 KB Output is correct
10 Correct 149 ms 2032 KB Output is correct
11 Correct 147 ms 1848 KB Output is correct
12 Correct 208 ms 2840 KB Output is correct
13 Correct 360 ms 1940 KB Output is correct
14 Correct 316 ms 2112 KB Output is correct
15 Correct 163 ms 2084 KB Output is correct
16 Correct 145 ms 2100 KB Output is correct
17 Correct 147 ms 1904 KB Output is correct
18 Correct 173 ms 2472 KB Output is correct
19 Correct 327 ms 2016 KB Output is correct
20 Correct 151 ms 2072 KB Output is correct
21 Correct 186 ms 2712 KB Output is correct
22 Correct 149 ms 1972 KB Output is correct
23 Correct 313 ms 1812 KB Output is correct
24 Correct 150 ms 1984 KB Output is correct
25 Correct 228 ms 3164 KB Output is correct