Submission #679875

#	Time	Username	Problem	Language	Result	Execution time	Memory
679875		vjudge1	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	38 ms	18240 KiB

uzastopni

#define taskname "Uzastopni"
#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e4 + 10;
vector<int> adj[maxn];
bitset<101> dp[maxn][105];
int a[maxn], n;

void DFS(int u, int p = -1)
{
    for (int i=1; i<=100; i++) dp[u][i].set(i-1);
    sort(adj[u].begin(), adj[u].end(), [](int x, int y) {return a[x] < a[y];});
    bool f = 0;
    for (int v: adj[u]) if (v != p)
    {
        DFS(v, u);
        if (!f && a[v] >= a[u])
        {
            f = 1;
            for (int l=1; l<=100; l++)
            {
                int val = dp[u][l][a[u]-1];
                dp[u][l].reset();
                if (val) dp[u][l].set(a[u]);
            }
        }
        for (int l=1; l<=a[v]; l++)
            for (int r=l-1; r<a[v]; r++)
                if (dp[u][l][r]) dp[u][l] |= dp[v][r+1];
    }
    if (!f)
    {
        for (int l=1; l<=100; l++)
        {
            int val = dp[u][l][a[u]-1];
            dp[u][l].reset();
            if (val) dp[u][l].set(a[u]);
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n;
    for (int i=1, x; i<=n; i++) cin>>x, dp[i][x].set(x), a[i] = x;
    for (int i=1, u, v; i<n; i++) cin>>u>>v, adj[u].emplace_back(v), adj[v].emplace_back(u);
    DFS(1);
    int ans = 0;
    for (int i=1; i<=100; i++) ans += dp[1][i].count();
    cout<<ans;
}

• Subtask 1: 160 / 160