Submission #3989621


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧  
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     
    /   \     | |     
    /   / ̄ ̄ ̄ ̄/  |  
  __(__ニつ/     _/ .| .|____  
     \/____/ (u ⊃  
---------------------------------------------------------------------------------------------------*/










int N, A[5010];
vector<int> E[5010];
//---------------------------------------------------------------------------------------------------
vector<pair<ll, int>> dp[5010];
int sz[5010];
void marge(int cu, int to) {
    vector<pair<ll, int>> res(sz[cu] + sz[to] + 1, { infl,0 });
    rep(cui, 0, sz[cu]) rep(toi, 0, sz[to]) {
        // くっつける
        chmin(res[cui + toi].first, dp[cu][cui].first + dp[to][toi].first);
        if (dp[cu][cui].second and dp[to][toi].second) res[cui + toi].second = 1;

        // くっつけない
        if (dp[to][toi].first < 0 or dp[to][toi].second) chmin(res[cui + toi + 1].first, dp[cu][cui].first);
        if ((dp[to][toi].first < 0 or dp[to][toi].second) and dp[cu][cui].second) res[cui + toi + 1].second = 1;
    }
    swap(dp[cu], res);
    sz[cu] += sz[to] + 1;
}
//---------------------------------------------------------------------------------------------------
void dfs(int cu, int pa = -1) {
    sz[cu] = 1;
    dp[cu].resize(1);
    dp[cu][0] = { A[cu], 0 < A[cu] };
    fore(to, E[cu]) if (to != pa) {
        dfs(to, cu);
        marge(cu, to);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    dfs(0);
    int ans = inf;
    rep(i, 0, sz[0]) if (dp[0][i].first < 0 or dp[0][i].second) chmin(ans, i);
    cout << ans << endl;
    
}

Submission Info

Submission Time
Task E - Attack to a Tree
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 600
Code Size 2861 Byte
Status AC
Exec Time 217 ms
Memory 327040 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 5
AC × 101
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-05.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, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt, 68.txt, 69.txt, 70.txt, 71.txt, 72.txt, 73.txt, 74.txt, 75.txt, 76.txt, 77.txt, 78.txt, 79.txt, 80.txt, 81.txt, 82.txt, 83.txt, 84.txt, 85.txt, 86.txt, 87.txt, 88.txt, 89.txt, 90.txt, 91.txt, 92.txt, 93.txt, 94.txt, 95.txt, 96.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-05.txt
Case Name Status Exec Time Memory
01.txt AC 144 ms 1412 KB
02.txt AC 144 ms 1420 KB
03.txt AC 110 ms 4060 KB
04.txt AC 111 ms 3360 KB
05.txt AC 186 ms 233596 KB
06.txt AC 157 ms 163456 KB
07.txt AC 170 ms 196864 KB
08.txt AC 212 ms 318208 KB
09.txt AC 144 ms 1412 KB
10.txt AC 141 ms 1412 KB
11.txt AC 109 ms 3228 KB
12.txt AC 114 ms 4248 KB
13.txt AC 206 ms 287684 KB
14.txt AC 180 ms 222592 KB
15.txt AC 200 ms 290816 KB
16.txt AC 185 ms 249600 KB
17.txt AC 134 ms 1412 KB
18.txt AC 110 ms 3736 KB
19.txt AC 202 ms 282952 KB
20.txt AC 173 ms 215552 KB
21.txt AC 134 ms 1412 KB
22.txt AC 111 ms 3556 KB
23.txt AC 165 ms 187904 KB
24.txt AC 162 ms 199040 KB
25.txt AC 144 ms 1412 KB
26.txt AC 113 ms 2768 KB
27.txt AC 164 ms 177024 KB
28.txt AC 171 ms 210944 KB
29.txt AC 142 ms 1412 KB
30.txt AC 115 ms 2952 KB
31.txt AC 159 ms 155264 KB
32.txt AC 202 ms 291968 KB
33.txt AC 134 ms 1420 KB
34.txt AC 94 ms 2744 KB
35.txt AC 156 ms 177536 KB
36.txt AC 169 ms 235264 KB
37.txt AC 139 ms 1420 KB
38.txt AC 114 ms 2916 KB
39.txt AC 175 ms 205568 KB
40.txt AC 166 ms 201344 KB
41.txt AC 140 ms 1420 KB
42.txt AC 109 ms 3236 KB
43.txt AC 166 ms 176768 KB
44.txt AC 199 ms 293248 KB
45.txt AC 139 ms 1420 KB
46.txt AC 109 ms 3616 KB
47.txt AC 157 ms 157936 KB
48.txt AC 178 ms 234752 KB
49.txt AC 141 ms 1420 KB
50.txt AC 117 ms 3876 KB
51.txt AC 159 ms 154752 KB
52.txt AC 184 ms 243968 KB
53.txt AC 144 ms 1420 KB
54.txt AC 105 ms 3452 KB
55.txt AC 167 ms 157312 KB
56.txt AC 182 ms 221184 KB
57.txt AC 110 ms 4172 KB
58.txt AC 124 ms 3300 KB
59.txt AC 163 ms 156240 KB
60.txt AC 157 ms 150764 KB
61.txt AC 125 ms 3716 KB
62.txt AC 113 ms 2808 KB
63.txt AC 166 ms 154792 KB
64.txt AC 149 ms 143488 KB
65.txt AC 112 ms 3868 KB
66.txt AC 141 ms 2716 KB
67.txt AC 146 ms 110076 KB
68.txt AC 158 ms 138360 KB
69.txt AC 127 ms 2868 KB
70.txt AC 136 ms 2584 KB
71.txt AC 183 ms 188868 KB
72.txt AC 136 ms 87048 KB
73.txt AC 135 ms 1540 KB
74.txt AC 111 ms 2420 KB
75.txt AC 156 ms 162048 KB
76.txt AC 165 ms 198528 KB
77.txt AC 134 ms 1420 KB
78.txt AC 110 ms 4508 KB
79.txt AC 161 ms 179968 KB
80.txt AC 189 ms 277248 KB
81.txt AC 142 ms 1420 KB
82.txt AC 115 ms 3264 KB
83.txt AC 161 ms 156032 KB
84.txt AC 214 ms 327040 KB
85.txt AC 144 ms 1412 KB
86.txt AC 113 ms 3912 KB
87.txt AC 193 ms 251752 KB
88.txt AC 185 ms 255744 KB
89.txt AC 115 ms 4056 KB
90.txt AC 110 ms 3248 KB
91.txt AC 175 ms 198400 KB
92.txt AC 198 ms 269544 KB
93.txt AC 115 ms 3048 KB
94.txt AC 111 ms 3720 KB
95.txt AC 206 ms 286020 KB
96.txt AC 217 ms 321528 KB
sample-01.txt AC 1 ms 512 KB
sample-02.txt AC 1 ms 512 KB
sample-03.txt AC 1 ms 512 KB
sample-04.txt AC 1 ms 512 KB
sample-05.txt AC 1 ms 512 KB