제출 #675176

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
675176		vjudge1	Uzastopni (COCI15_uzastopni)	C++14	160 / 160	124 ms	24412 KiB

uzastopni

#include <bits/stdc++.h>

#define ii pair<int,int>
#define fi first
#define se second

using namespace std;

int n, v[10005];
vector<int> V[10005],q[105];
vector<ii> s[10005];
bitset<105> f[10005][105];

void Dfs(int x)
{
    for(int y : V[x])  Dfs(y);
    for(int i = 0; i <= 100; i++) q[i].clear();

    for(int y : V[x])
    {
        for(ii it : s[y])
        q[it.fi].push_back(it.se);
    }

    for(int l = 100; l >= 1; l--)
    {
            if (l == v[x])
            {
                f[x][l] |= f[x][l + 1];
                f[x][l].set(l);
            }
            else
            {
                for(int r : q[l])
                if (r < v[x] || l > v[x])
                {
                    f[x][l] |= f[x][r + 1];
                    f[x][l].set(r);
                }
            }

        for(int r = 100; r >= l; r--) if(f[x][l][r] && v[x] >= l && v[x] <= r) s[x].push_back({l, r});
    }
}

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

    cin >> n;
    for(int i = 0; i < n; i++) cin >> v[i];

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

    Dfs(0);

    cout << s[0].size();

    return 0;
}

• Subtask 1: 160 / 160