oj.uz

Submission #65101

# Submission time Handle Problem Language Result Execution time Memory
65101 2018-08-06T15:52:40 Z forestryks Uzastopni (COCI15_uzastopni) C++14
160 / 160
 171 ms 9304 KB 
///////////////////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;

// #define int long long

#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define FILE_IO(x) freopen((string(x) + ".in").c_str(), "r", stdin); freopen((string(x) + ".out").c_str(), "w", stdout)
#define f first
#define s second
#define x1 x1qwer
#define y1 y1qwer
#define right right123
#define left left123
#define foreach(it, v) for (auto it : v)
#define rep(it, n) for (int it = 0; it < n; ++it)
#define forin(it, l, r) for (int it = l; it < r; ++it)
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double DINF = numeric_limits<double>::infinity();
const ll MOD = 1e9 + 7;
const double EPS = 1e-7;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
mt19937 mmtw_(MOD);
uniform_int_distribution<ll> rd_;
ll randomll() { return rd_(mmtw_);}
ll rnd(ll x, ll y) { return rd_(mmtw_) % (y - x + 1) + x; }
template <class T> T fact(T n) { if (n == 1) return 1; return n * fact(n - 1); }
////////////////////////////////////////////////////////////////////////////////////////////////

const int MAXN = 1e4 + 5;
const int MAXK = 105;

int n;
int a[MAXN];
bitset<MAXK> bs[MAXK];
vector<int> r[MAXK];
vector<int> g[MAXN];
vector<pair<int, int>> seg[MAXN];

void dfs(int v) {
    for (auto to : g[v]) {
        dfs(to);
    }

    rep(i, MAXK) {
        bs[i].reset();
        r[i].clear();
    }

    for (auto to : g[v]) {
        for (auto it : seg[to]) {
            r[it.f].push_back(it.s);
        }
    }

    for (int left = MAXK - 1; left >= 1; --left) {
        if (left == a[v]) {
            bs[left] |= bs[left + 1];
            bs[left].set(left);
        } else {
            for (auto right : r[left]) {
                if (right < a[v] || left > a[v]) {
                    bs[left] |= bs[right + 1];
                    bs[left].set(right);
                }
            }
        }

        for (int right = left; right < MAXK; ++right) {
            if (bs[left].test(right) && left <= a[v] && a[v] <= right) {
                seg[v].push_back({left, right});
            }
        }
    }
}

int main() {
    FAST_IO;
    cin >> n;
    rep(i, n) {
        cin >> a[i];
    }

    rep(i, n - 1) {
        int p, q;
        cin >> p >> q;
        g[p - 1].push_back(q - 1);
    }

    dfs(0);
    cout << seg[0].size() << endl;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 888 KB Output is correct
2 Correct 5 ms 1008 KB Output is correct
3 Correct 4 ms 1008 KB Output is correct
4 Correct 4 ms 1008 KB Output is correct
5 Correct 5 ms 1040 KB Output is correct
6 Correct 0 ms 1104 KB Output is correct
7 Correct 5 ms 1104 KB Output is correct
8 Correct 5 ms 1208 KB Output is correct
9 Correct 6 ms 1208 KB Output is correct
10 Correct 4 ms 1240 KB Output is correct
11 Correct 123 ms 1780 KB Output is correct
12 Correct 171 ms 2044 KB Output is correct
13 Correct 162 ms 2280 KB Output is correct
14 Correct 142 ms 8948 KB Output is correct
15 Correct 150 ms 9208 KB Output is correct
16 Correct 170 ms 9304 KB Output is correct
17 Correct 140 ms 9304 KB Output is correct
18 Correct 147 ms 9304 KB Output is correct
19 Correct 157 ms 9304 KB Output is correct
20 Correct 146 ms 9304 KB Output is correct