Submission #472071

#	Time	Username	Problem	Language	Result	Execution time	Memory
472071		SirCovidThe19th	Uzastopni (COCI15_uzastopni)	C++17	80 / 160	94 ms	18756 KiB

uzastopni

#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 / 160