oj.uz

Submission #59742

# Submission time Handle Problem Language Result Execution time Memory
59742 2018-07-23T03:15:43 Z Benq Museum (CEOI17_museum) C++11
100 / 100
 835 ms 204372 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 10001;
 
int n,k,x;
vpi adj[MX];
vi bes[MX][2];

vi bet(vi a, vi b) {
    F0R(i,sz(a)) a[i] = min(a[i],b[i]);
    return a;
}

vi conv(vi a, vi b) {
    vi res(sz(a)+sz(b)-1);
    F0R(i,sz(res)) res[i] = MOD;
    F0R(i,sz(a)) F0R(j,sz(b)) res[i+j] = min(res[i+j],a[i]+b[j]);
    return res;
}

void comb(int a, int b) {
    bes[a][0] = bet(conv(bes[a][0],bes[b][1]),conv(bes[a][1],bes[b][0]));
    bes[a][1] = conv(bes[a][1],bes[b][1]);
}

void dfs(int a, int b) {
    bes[a][0] = bes[a][1] = {0,0};
    for (auto x: adj[a]) if (x.f != b) {
        dfs(x.f,a);
        FOR(i,1,sz(bes[x.f][0])) {
            bes[x.f][0][i] += x.s;
            bes[x.f][1][i] += 2*x.s;
        }
        comb(a,x.f);
    }
    /*cout << a << " | ";
    for (int i: bes[a][0]) cout << i << " ";
        cout << "\n";*/
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k >> x;
    F0R(i,n-1) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].pb({b,c}), adj[b].pb({a,c});
    }
    dfs(x,0);
    cout << bes[x][0][k];
}
 
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 4488 KB Output is correct
2 Correct 190 ms 5144 KB Output is correct
3 Correct 608 ms 204372 KB Output is correct
4 Correct 325 ms 204372 KB Output is correct
5 Correct 209 ms 204372 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 4488 KB Output is correct
2 Correct 190 ms 5144 KB Output is correct
3 Correct 608 ms 204372 KB Output is correct
4 Correct 325 ms 204372 KB Output is correct
5 Correct 209 ms 204372 KB Output is correct
6 Correct 234 ms 204372 KB Output is correct
7 Correct 487 ms 204372 KB Output is correct
8 Correct 835 ms 204372 KB Output is correct
9 Correct 553 ms 204372 KB Output is correct
10 Correct 290 ms 204372 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1128 KB Output is correct
3 Correct 3 ms 1184 KB Output is correct
4 Correct 3 ms 1184 KB Output is correct
5 Correct 3 ms 1184 KB Output is correct
6 Correct 217 ms 4488 KB Output is correct
7 Correct 190 ms 5144 KB Output is correct
8 Correct 608 ms 204372 KB Output is correct
9 Correct 325 ms 204372 KB Output is correct
10 Correct 209 ms 204372 KB Output is correct
11 Correct 234 ms 204372 KB Output is correct
12 Correct 487 ms 204372 KB Output is correct
13 Correct 835 ms 204372 KB Output is correct
14 Correct 553 ms 204372 KB Output is correct
15 Correct 290 ms 204372 KB Output is correct
16 Correct 225 ms 204372 KB Output is correct
17 Correct 218 ms 204372 KB Output is correct
18 Correct 483 ms 204372 KB Output is correct
19 Correct 715 ms 204372 KB Output is correct
20 Correct 248 ms 204372 KB Output is correct
21 Correct 485 ms 204372 KB Output is correct
22 Correct 229 ms 204372 KB Output is correct
23 Correct 623 ms 204372 KB Output is correct
24 Correct 212 ms 204372 KB Output is correct
25 Correct 734 ms 204372 KB Output is correct