제출 #198129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
198129		brcode	Uzastopni (COCI15_uzastopni)	C++14	160 / 160	142 ms	19636 KiB

uzastopni

#include <iostream>
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1e5+5;
int arr[MAXN];
int n;
vector<int> v1[MAXN];
bitset<100> dp[MAXN][101];
void dfs(int curr,int par){
    for(int x:v1[curr]){
        if(x!=par){
            dfs(x,curr);
        }
    }
    for(int i=100;i>=1;i--){
        if(arr[curr] == i){
            dp[curr][i] = dp[curr][i+1];
            dp[curr][i][i] = 1;
        }
        for(int j=i;j<=100;j++){
            if(dp[curr][i][j]){
                dp[curr][i]|=dp[curr][j+1];
            }
        }
    }
    if(arr[curr]!=1){
        for(int i=100;i>=1;i--){
            if(dp[curr][i][arr[curr]-1]){
                dp[par][i]|=dp[curr][arr[curr]];
            }
        }
    }
    dp[par][arr[curr]]|=dp[curr][arr[curr]];
    int tempans = 0;
    for(int i=1;i<=5;i++){
        tempans+=dp[curr][i].count();
    }
    //cout<<tempans<<endl;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        v1[x].push_back(y);
        v1[y].push_back(x);
    }
    dfs(1,100001);
    int ans = 0;
    for(int i=1;i<=100;i++){
        ans+=dp[100001][i].count();
        //cout<<dp[1][i]<<endl;
    }
    cout<<ans<<endl;
}

• Subtask 1: 160 / 160