oj.uz

Submission #996252

# Submission time Handle Problem Language Result Execution time Memory
996252 2024-06-10T09:43:23 Z vjudge1 Uzastopni (COCI15_uzastopni) C++17
160 / 160
 83 ms 18268 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define lwb lower_bound
#define upb upper_bound

#define TASKNAME "NAME"

void init()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ///freopen(TASKNAME".INP","r",stdin); freopen(TASKNAME".OUT","w",stdout);
}

const int SZ = 1e4+5, MAXM = 1e2+5;
const ll INF = INT_MAX / 2, MOD = 1e9+7, INFLL = 2e18;
const double epsilon = 1e-3;

int n, a[SZ];
vector<int> adj[SZ];
bitset<MAXM> dp[SZ][MAXM], b[MAXM];

void dfs(int u)
{
    dp[u][a[u]][a[u]] = 1;
    for(int v : adj[u])
    {
        dfs(v);
    }
    for(int i = 1; i <= 100; i++) b[i].reset();
    for(int v : adj[u])
    {
        for(int i = 1; i <= 100; i++)
        {
            b[i] |= dp[v][i];
        }
    }
    for(int i = 1; i <= 100; i++)
    {
        for(int j = i+1; j <= 100; j++)
        {
            if(b[i][j-1]) b[i] |= b[j];
        }
    }
    for(int i = 1; i <= a[u]; i++)
    {
        for(int j = a[u]; j <= 100; j++)
        {
            if((i == a[u] || b[i][a[u] - 1]) && (j == a[u] || b[a[u]+1][j])) dp[u][i][j] = 1;
        }
    }
}

int main()
{
    init();
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for(int i = 1; i < n; i++)
    {
        int u,v;
        cin >> u >> v;
        adj[u].pb(v);
    }
    dfs(1);
    int res = 0;
    for(int i = 1; i <= 100; i++)
    {
        res += dp[1][i].count();
    }
    cout << res;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 74 ms 17408 KB Output is correct
12 Correct 69 ms 17244 KB Output is correct
13 Correct 63 ms 17432 KB Output is correct
14 Correct 83 ms 18268 KB Output is correct
15 Correct 81 ms 18268 KB Output is correct
16 Correct 78 ms 18268 KB Output is correct
17 Correct 64 ms 17324 KB Output is correct
18 Correct 69 ms 17244 KB Output is correct
19 Correct 79 ms 17304 KB Output is correct
20 Correct 82 ms 17156 KB Output is correct