oj.uz

Submission #97771

# Submission time Handle Problem Language Result Execution time Memory
97771 2019-02-18T12:08:31 Z win11905 Uzastopni (COCI15_uzastopni) C++11
160 / 160
 217 ms 24184 KB 
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author win11905
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define iii tuple<int, int, int>
#define long long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

const int N = 1e4+1, K = 101;

class uzastopni {
private:
    int n, A[N];
    vector<int> g[N];
    vector<pii> S[N];
    queue<int> Q[K];
    bitset<K> dp[N][K];
    void dfs(int u) {
        for(int v : g[u]) dfs(v);
        for(int v : g[u]) for(pii x : S[v]) if(x.x != A[u]) Q[x.x].emplace(x.y);
        for(int l = K-1; l; --l) {
            if(l == A[u]) dp[u][l] |= dp[u][l+1], dp[u][l][l] = true;
            else while(!Q[l].empty()) {
                int r = Q[l].front(); Q[l].pop();
                if(A[u] < l || A[u] > r) dp[u][l] |= dp[u][r+1], dp[u][l][r] = true;
            }
            for(int r = K-1; r; --r) if(dp[u][l][r] && l <= A[u] && A[u] <= r) S[u].emplace_back(l, r);
        }
    }
public:
    void solve(istream& cin, ostream& cout) {
        cin >> n;
        for(int i = 1; i <= n; ++i) cin >> A[i];
        for(int i = 1, u, v; i < n; ++i) {
            cin >> u >> v;
            g[u].emplace_back(v);
        }
        dfs(1);
        cout << S[1].size();
    }
};

class Solver {
public:
    void solve(std::istream& in, std::ostream& out) {
        uzastopni *obj = new uzastopni();
        obj->solve(in, out);
    }
};

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    Solver solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16768 KB Output is correct
2 Correct 19 ms 16896 KB Output is correct
3 Correct 23 ms 16768 KB Output is correct
4 Correct 21 ms 16768 KB Output is correct
5 Correct 21 ms 16768 KB Output is correct
6 Correct 20 ms 16768 KB Output is correct
7 Correct 21 ms 16768 KB Output is correct
8 Correct 23 ms 16768 KB Output is correct
9 Correct 24 ms 16768 KB Output is correct
10 Correct 20 ms 16768 KB Output is correct
11 Correct 205 ms 17372 KB Output is correct
12 Correct 217 ms 17504 KB Output is correct
13 Correct 195 ms 17400 KB Output is correct
14 Correct 169 ms 24144 KB Output is correct
15 Correct 173 ms 24184 KB Output is correct
16 Correct 194 ms 24096 KB Output is correct
17 Correct 191 ms 17472 KB Output is correct
18 Correct 194 ms 17576 KB Output is correct
19 Correct 177 ms 19796 KB Output is correct
20 Correct 211 ms 19704 KB Output is correct