oj.uz

Submission #644253

# Submission time Handle Problem Language Result Execution time Memory
644253 2022-09-24T09:29:52 Z BackNoob Uzastopni (COCI15_uzastopni) C++14
160 / 160
 221 ms 18808 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 1e4 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
const int block_sz = 550;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}

int n;
int v[mxN];
bitset<107> dp[mxN][107];
bitset<107> dp1[107];
bitset<107> dp2[107];
vector<int> adj[mxN];

void dfs(int u, int p)
{
    dp[u][v[u]][v[u]] = true;
    for(int vv : adj[u]) {
        if(vv == p) continue;
        dfs(vv, u);

        for(int i = 1; i <= 100; i++) {
            for(int j = 1; j <= 100; j++) {
                if(dp[vv][i][j] == true && !(i <= v[u] && v[u] <= j)) {
                    dp[u][i][j] = true;
                }
            }
        }
    }

    for(int l = 100; l >= 1; l--) {
        for(int r = l; r <= 100; r++) {
            if(dp[u][l][r] == true) {
                dp[u][l] |= dp[u][r + 1];
            }
        }
    }

    for(int l = 1; l <= 100; l++) {
        for(int r = l; r <= 100; r++) {
            if(!(l <= v[u] && v[u] <= r)) dp[u][l][r] = false;
        }
    }

    for(int l = 1; l <= 100; l++) {
        for(int r = l; r <= 100; r++) {
            //if(dp[u][l][r] == true) cout << u << ' ' << l << ' ' << r << endl;
        }
    }

}

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> v[i];

    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    dfs(1, -1);

    int res = 0;
    for(int i = 1; i <= 100; i++) {
        for(int j = i; j <= 100; j++) {
            res += dp[1][i][j];
        }
    }

    cout << res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("task.inp", "r", stdin);
    //freopen("graph.out", "w", stdout);

    int tc = 1;
    //cin >> tc;
    while(tc--) {
        solve();
    }
    return 0;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 3 ms 696 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 3 ms 752 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 210 ms 17612 KB Output is correct
12 Correct 214 ms 17672 KB Output is correct
13 Correct 211 ms 17660 KB Output is correct
14 Correct 216 ms 18808 KB Output is correct
15 Correct 208 ms 18452 KB Output is correct
16 Correct 208 ms 18508 KB Output is correct
17 Correct 221 ms 17752 KB Output is correct
18 Correct 217 ms 17556 KB Output is correct
19 Correct 207 ms 17648 KB Output is correct
20 Correct 207 ms 17648 KB Output is correct