oj.uz

Submission #472099

# Submission time Handle Problem Language Result Execution time Memory
472099 2021-09-12T21:48:52 Z SirCovidThe19th Uzastopni (COCI15_uzastopni) C++17
160 / 160
 93 ms 18856 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 676 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 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 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 75 ms 17240 KB Output is correct
12 Correct 77 ms 17220 KB Output is correct
13 Correct 75 ms 17156 KB Output is correct
14 Correct 87 ms 18676 KB Output is correct
15 Correct 93 ms 18856 KB Output is correct
16 Correct 86 ms 18664 KB Output is correct
17 Correct 76 ms 17164 KB Output is correct
18 Correct 75 ms 17200 KB Output is correct
19 Correct 83 ms 17036 KB Output is correct
20 Correct 83 ms 17092 KB Output is correct