Submission #96782

#	Time	Username	Problem	Language	Result	Execution time	Memory
96782		Tieuphong	Uzastopni (COCI15_uzastopni)	C++11	160 / 160	117 ms	24056 KiB

uzastopni

/***************************************************************************/
/**********************  LANG TU HAO HOA  **********************************/
/***************************************************************************/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define sz(x) ((int) x.size())
#define PB push_back
#define PF push_front
#define MP make_pair
#define ll long long
#define F first
#define S second
#define maxc 1000000007
#define MOD 1000000007
#define base 107
#define eps 1e-6
#define pi acos(-1)
#define N 10004
#define V 102
#define task ""
#define remain(x) ((x > MOD) ? (x - MOD) : x)

using namespace std;

int n, c[N];

vector <int> ke[N], a[V];

vector <pii> dp[N];

bitset <V> dd[N][V];

void DFS(int u, int p)
{
    for (auto v : ke[u])
    {
        if (v == p) continue;
        DFS(v, u);
    }
    FOR(i, 1, 100) a[i].clear();
    for (auto v : ke[u])
        for (auto pa : dp[v])
            a[pa.F].PB(pa.S);
    FORD(L, 100, 1)
    {
        if (L == c[u])
        {
            dd[u][L] |= dd[u][L+1];
            dd[u][L].set(L);
        }
            else
            {
                for (auto R : a[L])
                    if (L > c[u] || c[u] > R)
                    {
                        dd[u][L] |= dd[u][R+1];
                        dd[u][L].set(R);
                    }
            }
        FORD(R, 100, L)
            if (dd[u][L].test(R) && L <= c[u] && c[u] <= R)
                dp[u].PB(MP(L, R));
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //freopen(task".inp", "r", stdin);
    //freopen(task".out", "w", stdout);
    cin >> n;
    FOR(i, 1, n) cin >> c[i];
    FOR(i, 1, n-1)
    {
        int u, v; cin >> u >> v;
        ke[u].PB(v);
        ke[v].PB(u);
    }
    DFS(1, -1);
    cout << sz(dp[1]);
    return 0;
}

• Subtask 1: 160 / 160