oj.uz

Submission #156399

# Submission time Handle Problem Language Result Execution time Memory
156399 2019-10-05T12:59:28 Z farmerboy Museum (CEOI17_museum) C++14
100 / 100
 936 ms 785268 KB 
/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/

#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define WHATIS(x) cout << #x << " is " << x << endl;
#define ERROR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << endl;
    err(++it, args...);
}

const ll MODBASE = 1000000007LL;
const int MAXN = 10010;
const int MAXM = 1010;
const int MAXK = 110;
const int MAXQ = 200010;

int n, k, dp[2][MAXN][MAXN], num[MAXN];
vector<II> a[MAXN];

void dfs(int u, int p) {
    dp[0][u][1] = dp[1][u][1] = 0;
    num[u] = 1;
    FOR(i,0,SZ(a[u])-1) {
        int v = a[u][i].FI;
        int c = a[u][i].SE;
        if (v == p) continue;
        dfs(v, u);
        FORE(j,num[u],0)
            FORE(p,num[v],1) {
                dp[0][u][j+p] = min(dp[0][u][j+p], dp[0][u][j] + dp[0][v][p] + 2 * c);
                dp[1][u][j+p] = min(dp[1][u][j+p], dp[1][u][j] + dp[0][v][p] + 2 * c);
                dp[1][u][j+p] = min(dp[1][u][j+p], dp[0][u][j] + dp[1][v][p] + c);
            }
        num[u] += num[v];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int x;
    cin >> n >> k >> x;
    FOR(i,1,n-1) {
        int u, v, c;
        cin >> u >> v >> c;
        a[u].emplace_back(II(v, c));
        a[v].emplace_back(II(u, c));
    }
    FOR(p,0,1) FOR(i,1,n) FOR(j,1,n) dp[p][i][j] = 1000000000;
    dfs(x, 0);
    cout << dp[1][x][k];
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 922 ms 784764 KB Output is correct
2 Correct 834 ms 784772 KB Output is correct
3 Correct 889 ms 785180 KB Output is correct
4 Correct 850 ms 784932 KB Output is correct
5 Correct 843 ms 784776 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 922 ms 784764 KB Output is correct
2 Correct 834 ms 784772 KB Output is correct
3 Correct 889 ms 785180 KB Output is correct
4 Correct 850 ms 784932 KB Output is correct
5 Correct 843 ms 784776 KB Output is correct
6 Correct 894 ms 784800 KB Output is correct
7 Correct 866 ms 785244 KB Output is correct
8 Correct 872 ms 784760 KB Output is correct
9 Correct 857 ms 784712 KB Output is correct
10 Correct 856 ms 784840 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 922 ms 784764 KB Output is correct
7 Correct 834 ms 784772 KB Output is correct
8 Correct 889 ms 785180 KB Output is correct
9 Correct 850 ms 784932 KB Output is correct
10 Correct 843 ms 784776 KB Output is correct
11 Correct 894 ms 784800 KB Output is correct
12 Correct 866 ms 785244 KB Output is correct
13 Correct 872 ms 784760 KB Output is correct
14 Correct 857 ms 784712 KB Output is correct
15 Correct 856 ms 784840 KB Output is correct
16 Correct 826 ms 784976 KB Output is correct
17 Correct 849 ms 784888 KB Output is correct
18 Correct 853 ms 784952 KB Output is correct
19 Correct 912 ms 784880 KB Output is correct
20 Correct 830 ms 784888 KB Output is correct
21 Correct 864 ms 785012 KB Output is correct
22 Correct 826 ms 784824 KB Output is correct
23 Correct 936 ms 784816 KB Output is correct
24 Correct 830 ms 784896 KB Output is correct
25 Correct 888 ms 785268 KB Output is correct