oj.uz

Submission #472082

# Submission time Handle Problem Language Result Execution time Memory
472082 2021-09-12T20:19:45 Z SirCovidThe19th Uzastopni (COCI15_uzastopni) C++17
160 / 160
 111 ms 18620 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){
    dp[i][A[i]][A[i]] = 1;
    for (int x : adj[i]){
        dfs(x); 
        FOR(j, 0, mv){
			if (j < A[i]) dp[i][j] |= dp[x][j] << (mv - A[i]) >> (mv - A[i]);
			if (j > A[i]) 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; 
        adj[a - 1].push_back(b - 1);
    }
    dfs(0);
    FOR(i, 0, mv) ans += dp[0][i].count();
    cout<<ans<<endl;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 78 ms 17152 KB Output is correct
12 Correct 74 ms 17088 KB Output is correct
13 Correct 75 ms 17152 KB Output is correct
14 Correct 87 ms 18604 KB Output is correct
15 Correct 87 ms 18512 KB Output is correct
16 Correct 111 ms 18620 KB Output is correct
17 Correct 74 ms 17092 KB Output is correct
18 Correct 74 ms 17036 KB Output is correct
19 Correct 83 ms 16988 KB Output is correct
20 Correct 84 ms 17016 KB Output is correct