oj.uz

Submission #1099241

# Submission time Handle Problem Language Result Execution time Memory
1099241 2024-10-11T02:45:23 Z anhthi Uzastopni (COCI15_uzastopni) C++14
160 / 160
 43 ms 10184 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define pb push_back
#define heap priority_queue
#define max_rng *max_element
#define min_rng *min_element
#define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)

template <class X, class Y>
    inline bool maximize(X &x, Y y) {
        return (x < y ? x = y, true : false);
    }

template <class X, class Y>
    inline bool minimize(X &x, Y y) {
        return (x > y ? x = y, true : false);
    }

template <class X>
    inline void compress(vector<X> &a) {
        sort(all(a));
        a.resize(unique(all(a)) - a.begin());
    }

int ctz(ll x) { return __builtin_ctzll(x); }
int lg(ll x) { return 63 - __builtin_clzll(x); }
int popcount(ll x) { return __builtin_popcount(x); }

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) {
    return l + abs((ll) rng()) % (r - l + 1);
}

const ll oo = (ll) 1e17;
const int inf = (ll) 1e9 + 7, mod = (ll) 1e9 + 7;

const int N = 1e4 + 5, M = 5555;

void add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
void sub(int &x, int y) { x -= y; if (x < 0) x += mod; }

int n, m;
int a[N];
vector<int> g[N];

vector<pair<int, int>> S[N];
void dfs(int u, int p) {
    int val = a[u];
    vector<pair<int, int>> left, right;
    for (int v : g[u]) if (v != p) {
        dfs(v, u);
        for (pair<int, int> i : S[v]) {
            if (i.second < val) left.pb(i);
            else if (i.first > val) right.pb(i);
        }
    }
    map<int, int> dpL, dpR;
    dpL[val] = dpR[val] = 1;
    sort(all(left)); reverse(all(left));
    for(pair<int, int> i : left) {
        dpL[i.first] += dpL[i.second + 1];
    }
    sort(all(right));
    for (pair<int, int> i : right) {
        dpR[i.second] += dpR[i.first - 1];
    }
    for (pair<int, int> i : dpL)
    for (pair<int, int> j : dpR) {
        if (i.second * j.second != 0)
            S[u].pb(mp(i.first, j.first));
    }
    compress(S[u]);
}

signed main(void) {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    rep(i, n) cin >> a[i];
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    dfs(1, 0);
    cout << sz(S[1]);

    return 0;   
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 936 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 0 ms 860 KB Output is correct
10 Correct 1 ms 920 KB Output is correct
11 Correct 6 ms 1628 KB Output is correct
12 Correct 5 ms 1628 KB Output is correct
13 Correct 5 ms 1724 KB Output is correct
14 Correct 39 ms 10184 KB Output is correct
15 Correct 43 ms 10068 KB Output is correct
16 Correct 39 ms 10072 KB Output is correct
17 Correct 6 ms 1628 KB Output is correct
18 Correct 5 ms 1628 KB Output is correct
19 Correct 10 ms 4160 KB Output is correct
20 Correct 10 ms 3928 KB Output is correct