oj.uz

Submission #776709

# Submission time Handle Problem Language Result Execution time Memory
776709 2023-07-08T07:38:59 Z GrindMachine Uzastopni (COCI15_uzastopni) C++17
160 / 160
 187 ms 18380 KB 
// Om Namah Shivaya

#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://github.com/MetalBall887/Competitive-Programming/blob/master/Olympiad/COCI/COCI%2015-uzastopni.cpp
edi

*/

const int MOD = 1e9 + 7;
const int N = 1e4 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
const int K = 100 + 5;

bitset<K> dp[N][K];
vector<int> adj[N];
vector<int> a(N);
vector<int> here[K];

void dfs(int u){
    trav(v,adj[u]){
        dfs(v);
    }

    rep1(i,K-1){
        here[i].clear();
    }

    trav(v,adj[u]){
        rep1(l,K-1){
            for(int r = l; r < K; ++r){
                if(dp[v][l][r]){
                    if(l > a[u] or r < a[u]){
                        here[l].pb(r);
                    }
                }
            }
        }
    }

    here[a[u]].pb(a[u]);

    rev(l,K-1,1){
        trav(r,here[l]){
            dp[u][l][r] = 1;
            if(r+1 < K){
                dp[u][l] |= dp[u][r+1];
            }
        }
    }

    rep1(l,K-1){
        for(int r = l; r < K; ++r){
            if(r < a[u] or l > a[u]){
                dp[u][l][r] = 0;
            }
        }
    }
}

void solve(int test_case)
{
    int n; cin >> n;
    rep1(i,n) cin >> a[i];
    rep1(i,n-1){
        int u,v; cin >> u >> v;
        adj[u].pb(v);
    }

    dfs(1);

    int ans = 0;
    rep1(l,K-1){
        for(int r = l; r < K; ++r){
            ans += dp[1][l][r];
        }
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    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 2 ms 596 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 664 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 740 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 183 ms 17188 KB Output is correct
12 Correct 187 ms 17316 KB Output is correct
13 Correct 184 ms 17128 KB Output is correct
14 Correct 181 ms 18380 KB Output is correct
15 Correct 180 ms 18296 KB Output is correct
16 Correct 176 ms 18276 KB Output is correct
17 Correct 184 ms 17148 KB Output is correct
18 Correct 184 ms 17152 KB Output is correct
19 Correct 174 ms 17124 KB Output is correct
20 Correct 173 ms 16972 KB Output is correct