제출 #1319723

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319723		ee23b179_cp	Uzastopni (COCI15_uzastopni)	C++20	160 / 160	52 ms	23968 KiB

uzastopni

#include <bits/stdc++.h>
using namespace std;

const int N=10005;
int n,v[N];
vector<int> g[N];
vector<pair<int,int>> s[N];
bitset<101> B[N][101];
vector<int> q[101];

void dfs(int u,int p){
    for(int x:g[u]) if(x!=p) dfs(x,u);

    for(int i=1;i<=100;i++) q[i].clear();
    for(int x:g[u]) if(x!=p)
        for(auto &e:s[x]) q[e.first].push_back(e.second);

    for(int l=100;l>=1;l--){
        if(l==v[u]){
            B[u][l]|=B[u][l+1];
            B[u][l].set(l);
        }else{
            for(int r:q[l])
                if(r<v[u]||l>v[u]){
                    B[u][l]|=B[u][r+1];
                    B[u][l].set(r);
                }
        }
        if(l<=v[u])
            for(int r=100;r>=l;r--)
                if(v[u]>=l&&v[u]<=r&&B[u][l][r])
                    s[u].push_back({l,r});
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>v[i];
    for(int i=1,u,w;i<n;i++){
        cin>>u>>w;
        g[u].push_back(w);
        g[w].push_back(u);
    }
    dfs(1,0);
    cout<<s[1].size();
}

• Subtask 1: 160 / 160