제출 #472099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
472099		SirCovidThe19th	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	93 ms	18856 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){
    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 / 160