Submission #10033561


Source Code Expand

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
const long double PI = acos(-1.0L);
const long long MOD = 1000000007LL;
//const long long MOD = 998244353LL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true;} return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true;} return false; }
///////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N,M,K; cin >> N >> M >> K;
    vector<vector<int>> G(N);
    int s;
    rep(i,N) {
        int p; cin >> p;
        p--;
        if (p < 0) {
            s = i;
            continue;
        }
        G[p].emplace_back(i);
    }

    vector<int> dist(N);
    queue<int> que;
    que.emplace(s);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (auto nv : G[v]) {
            dist[nv] = dist[v]+1;
            que.emplace(nv);
        }
    }
    if (K < M) {
        cout << -1 << endl;
        return 0;
    }
    K -= M;
    reverse(all(dist));
    vector<vector<bitset<100001>>> dp(N+1, vector<bitset<100001>>(M+1));
    dp[0][0][0] = 1;
    rep(i,N) {
        rep(j,M+1) {
            dp[i+1][j] = dp[i][j];
            if (j > 0) dp[i+1][j] |= dp[i][j-1]<<dist[i];
        } 
    }
    if (!dp[N][M].test(K)) {
        cout << -1 << endl;
        return 0;
    }
    vector<int> ans;
    for (int i = N-1; i >= 0; --i) {
        if (M > 0 && K - dist[i] >= 0 && dp[i][M-1].test(K-dist[i])) {
            ans.emplace_back(N-i);
            K -= dist[i];
            M--;
        }
    }

    for (auto i : ans) cout << i << " ";
    cout << endl;

}

Submission Info

Submission Time
Task F - Coins on the tree
User minato_
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2005 Byte
Status WA
Exec Time 859 ms
Memory 1015552 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 2
AC × 8
WA × 34
Set Name Test Cases
Sample s1.txt, s2.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt WA 31 ms 33152 KB
02.txt AC 3 ms 2176 KB
03.txt WA 12 ms 13056 KB
04.txt WA 30 ms 31360 KB
05.txt WA 11 ms 11776 KB
06.txt WA 59 ms 62848 KB
07.txt WA 106 ms 113152 KB
08.txt WA 218 ms 236288 KB
09.txt WA 162 ms 174336 KB
10.txt WA 465 ms 507008 KB
11.txt WA 85 ms 90496 KB
12.txt WA 260 ms 283008 KB
13.txt WA 373 ms 403456 KB
14.txt WA 319 ms 347136 KB
15.txt WA 89 ms 95360 KB
16.txt WA 501 ms 546048 KB
17.txt WA 526 ms 575744 KB
18.txt WA 677 ms 773248 KB
19.txt WA 780 ms 909824 KB
20.txt WA 722 ms 826496 KB
21.txt WA 568 ms 623744 KB
22.txt WA 859 ms 1015552 KB
23.txt WA 795 ms 923136 KB
24.txt WA 813 ms 958080 KB
25.txt WA 816 ms 961408 KB
26.txt WA 567 ms 623744 KB
27.txt WA 597 ms 661120 KB
28.txt WA 619 ms 694144 KB
29.txt WA 639 ms 716672 KB
30.txt WA 629 ms 715264 KB
31.txt AC 42 ms 43776 KB
32.txt AC 8 ms 8064 KB
33.txt AC 32 ms 34048 KB
34.txt AC 6 ms 6528 KB
35.txt AC 96 ms 102528 KB
36.txt WA 45 ms 49536 KB
37.txt WA 8 ms 8960 KB
38.txt WA 4 ms 3456 KB
39.txt WA 9 ms 10496 KB
40.txt WA 10 ms 12416 KB
s1.txt AC 1 ms 512 KB
s2.txt AC 1 ms 512 KB