oj.uz

Submission #96782

# Submission time Handle Problem Language Result Execution time Memory
96782 2019-02-12T02:01:53 Z Tieuphong Uzastopni (COCI15_uzastopni) C++11
160 / 160
 117 ms 24056 KB 
/***************************************************************************/
/**********************  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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 3 ms 892 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 3 ms 1016 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 85 ms 17504 KB Output is correct
12 Correct 83 ms 17528 KB Output is correct
13 Correct 84 ms 17588 KB Output is correct
14 Correct 97 ms 24056 KB Output is correct
15 Correct 117 ms 23872 KB Output is correct
16 Correct 99 ms 23928 KB Output is correct
17 Correct 88 ms 17616 KB Output is correct
18 Correct 85 ms 17656 KB Output is correct
19 Correct 84 ms 20088 KB Output is correct
20 Correct 85 ms 20088 KB Output is correct