oj.uz

Submission #411115

# Submission time Handle Problem Language Result Execution time Memory
411115 2021-05-24T11:46:54 Z iANikzad Uzastopni (COCI15_uzastopni) C++14
160 / 160
 113 ms 30764 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
#define int long long

typedef long long ll;
typedef long double ld;

const int maxn = 1e4 + 7;
const int maxk = 1e2 + 7;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const int mlog = 20;
const int SQ = 400;

int a[maxn];

vector<int> adj[maxn], q[maxn];
vector<pii> s[maxn];

bitset<maxk> dp[maxn][maxk];

void dfs(int v)
{
    for(int u : adj[v]) dfs(u);

    for(int i = 1; i < maxk; i++)
        q[i].clear();

    for(int u : adj[v]) for(pii p : s[u]) q[p.F].pb(p.S);

    for(int l = maxk - 1; l >= 1; l--)
    {
        if(l == a[v])
        {
            dp[v][l] |= dp[v][l + 1];
            dp[v][l][l] = true;
        }
        else
        {
            for(int r : q[l])
            {
                if(a[v] < l || a[v] > r)
                {
                    dp[v][l] |= dp[v][r + 1];
                    dp[v][l][r] = true;
                }
            }
        }

        for(int r = maxk - 1; r >= l; r--) if(dp[v][l][r] && a[v] >= l && a[v] <= r) s[v].pb({l, r});
    }
}

int32_t main()
{
    FAST;

    int n; 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);

    cout << s[1].size() << "\n";

    return 0;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 2 ms 1100 KB Output is correct
3 Correct 2 ms 1100 KB Output is correct
4 Correct 2 ms 1136 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 2 ms 1156 KB Output is correct
8 Correct 2 ms 1156 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 2 ms 1100 KB Output is correct
11 Correct 87 ms 18400 KB Output is correct
12 Correct 86 ms 18416 KB Output is correct
13 Correct 87 ms 18584 KB Output is correct
14 Correct 113 ms 30572 KB Output is correct
15 Correct 102 ms 30764 KB Output is correct
16 Correct 100 ms 30668 KB Output is correct
17 Correct 87 ms 18524 KB Output is correct
18 Correct 90 ms 18504 KB Output is correct
19 Correct 90 ms 22952 KB Output is correct
20 Correct 105 ms 22916 KB Output is correct