oj.uz

답안 #1084622

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1084622 2024-09-06T14:28:56 Z ShaShi Museum (CEOI17_museum) C++17
100 / 100
 419 ms 310828 KB 
#include <bits/stdc++.h>
 
#define int long long
 
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
 
#define F first 
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define endl "\n"
 
 
 
using namespace std;
typedef long long ll;
// typedef __int128_t lll;
typedef long double ld;
 
const int MAXN = (int)1e4 + 7;
const int MOD = 998244353;
const ll INF = (ll)1e18 + 7;
const int LG = 20;


int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, flag, q, ans, flag2;
int arr[MAXN], arr2[MAXN], sz[MAXN];
vector<pii> adj[MAXN];
vector<int> dp[2][MAXN];


void DFS(int v, int p=0) {
    dp[0][v] = {0, 0}; dp[1][v] = {0, 0}; sz[v] = 1;

    for (auto cur:adj[v]) {
        int u = cur.F, w = cur.S;

        if (u == p) continue;

        DFS(u, v);

        vector<int> pd[2]; 
        pd[0].resize(sz[v]+sz[u]+1); fill(all(pd[0]), INF);
        pd[1].resize(sz[v]+sz[u]+1); fill(all(pd[1]), INF);

        for (int x=0; x<=sz[v]; x++) {
            for (int y=0; y<=sz[u]; y++) {
                pd[1][x+y] = min(pd[1][x+y], dp[1][v][x]+dp[1][u][y]+2*w);
                pd[0][x+y] = min(pd[0][x+y], dp[1][v][x]+dp[0][u][y]+w);
                pd[0][x+y] = min(pd[0][x+y], dp[0][v][x]+dp[1][u][y]+2*w);

                if (!y) pd[1][x] = min(pd[1][x], dp[1][v][x]);
                if (!y) pd[0][x] = min(pd[0][x], dp[0][v][x]);
            }
        }

        dp[0][v] = pd[0]; dp[1][v] = pd[1]; sz[v] += sz[u];
    }
}


int32_t main() {
    #ifdef LOCAL
    freopen("inp.in", "r", stdin);
    freopen("res.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    cin >> n >> k >> m;

    for (int i=1; i<n; i++) {
        cin >> u >> v >> w;

        adj[u].pb({v, w}); adj[v].pb({u, w});
    }

    DFS(m);

    cout << dp[0][m][k] << endl;


    return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 6448 KB Output is correct
2 Correct 101 ms 7248 KB Output is correct
3 Correct 298 ms 310828 KB Output is correct
4 Correct 162 ms 98060 KB Output is correct
5 Correct 114 ms 24908 KB Output is correct

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 6448 KB Output is correct
2 Correct 101 ms 7248 KB Output is correct
3 Correct 298 ms 310828 KB Output is correct
4 Correct 162 ms 98060 KB Output is correct
5 Correct 114 ms 24908 KB Output is correct
6 Correct 103 ms 5072 KB Output is correct
7 Correct 227 ms 181072 KB Output is correct
8 Correct 419 ms 3244 KB Output is correct
9 Correct 298 ms 3448 KB Output is correct
10 Correct 126 ms 4836 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 102 ms 6448 KB Output is correct
7 Correct 101 ms 7248 KB Output is correct
8 Correct 298 ms 310828 KB Output is correct
9 Correct 162 ms 98060 KB Output is correct
10 Correct 114 ms 24908 KB Output is correct
11 Correct 103 ms 5072 KB Output is correct
12 Correct 227 ms 181072 KB Output is correct
13 Correct 419 ms 3244 KB Output is correct
14 Correct 298 ms 3448 KB Output is correct
15 Correct 126 ms 4836 KB Output is correct
16 Correct 101 ms 7760 KB Output is correct
17 Correct 100 ms 7504 KB Output is correct
18 Correct 185 ms 117588 KB Output is correct
19 Correct 322 ms 3272 KB Output is correct
20 Correct 111 ms 5484 KB Output is correct
21 Correct 223 ms 171348 KB Output is correct
22 Correct 104 ms 6996 KB Output is correct
23 Correct 341 ms 3328 KB Output is correct
24 Correct 108 ms 5204 KB Output is correct
25 Correct 317 ms 307536 KB Output is correct