제출 #1179376

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179376		RandomUser	Uzastopni (COCI15_uzastopni)	C++20	160 / 160	287 ms	17904 KiB

uzastopni

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;

int n, a[N], ans = 0;
vector<int> G[N];
bitset<100> dp[N][101];

void dfs(int u, int p) {
    a[u]--;
    dp[u][a[u]][a[u]] = 1;

    for(int v : G[u]) {
        if(v == p) continue;
        dfs(v, u);
        for(int i=0; i<100; i++)
            for(int j=i; j<100; j++)
                if(!(i <= a[u] && a[u] <= j) && dp[v][i][j])
                    dp[u][i][j] = 1;
    }

    for(int i=99; i>=0; i--)
        for(int j=i; j<100; j++)
            if(dp[u][i][j]) dp[u][i] |= dp[u][j+1];

    for(int i=0; i<100; i++)
        for(int j=i; j<100; j++)
            if(j < a[u] || a[u] < i) dp[u][i][j] = 0;
}

int main() {
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];

    for(int i=1; i<n; i++) {
        int a, b; cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    dfs(1, 1);
    for(int i=0; i<100; i++)
        for(int j=i; j<100; j++) ans += dp[1][i][j];
    cout << ans << '\n';
}

• Subtask 1: 160 / 160