oj.uz

Submission #472071

# Submission time Handle Problem Language Result Execution time Memory
472071 2021-09-12T18:27:50 Z SirCovidThe19th Uzastopni (COCI15_uzastopni) C++17
80 / 160
 94 ms 18756 KB 
#include <bits/stdc++.h>
using namespace std; 

#define FOR(i, x, y) for (int i = x; i < y; i++)

const int mx = 10005, mv = 105;

int n, A[mx], ans; vector<int> adj[mx]; bitset<mv> dp[mx][mv];

void dfs(int i, int p){
    dp[i][A[i]][A[i]] = 1;
    for (int x : adj[i]) if (x != p){
        dfs(x, i);
        FOR(j, 0, mv) dp[i][j] |= dp[x][j];
    }
    for (int j = mv - 1; j; j--) FOR(k, j, mv - 1)
        if (dp[i][j][k]) dp[i][j] |= dp[i][k + 1];
    FOR(j, 0, mv){
        if (j <= A[i]) dp[i][j] = dp[i][j] >> A[i] << A[i];
        else dp[i][j].reset();
    }
}
int main(){
    cin >> n;
    FOR(i, 0, n) cin >> A[i];
    FOR(i, 0, n - 1){
        int a, b; cin >> a >> b; a--; b--;
        adj[a].push_back(b); adj[b].push_back(a);
    }
    dfs(0, 0);
    FOR(i, 0, mv) ans += dp[0][i].count();
    cout<<ans<<endl;
}

Subtask #1
80.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 2 ms 672 KB Output is correct
3 Incorrect 2 ms 588 KB Output isn't correct
4 Incorrect 1 ms 588 KB Output isn't correct
5 Incorrect 2 ms 716 KB Output isn't correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 1 ms 672 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Incorrect 94 ms 17400 KB Output isn't correct
12 Incorrect 92 ms 17472 KB Output isn't correct
13 Correct 90 ms 17368 KB Output is correct
14 Incorrect 93 ms 18756 KB Output isn't correct
15 Incorrect 92 ms 18752 KB Output isn't correct
16 Incorrect 94 ms 18676 KB Output isn't correct
17 Correct 92 ms 17412 KB Output is correct
18 Correct 88 ms 17404 KB Output is correct
19 Incorrect 91 ms 17424 KB Output isn't correct
20 Incorrect 91 ms 17352 KB Output isn't correct