oj.uz

Submission #841082

# Submission time Handle Problem Language Result Execution time Memory
841082 2023-09-01T08:49:19 Z hafo Uzastopni (COCI15_uzastopni) C++14
160 / 160
 127 ms 18640 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e4 + 7;
const ll oo = 1e18 + 69;
const int maxv = 1e2 + 7;

int n, a[maxn], u, v;
vector<int> g[maxn];
bitset<maxv> dp[maxn][maxv], f[maxv];

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

    for(int i = 1; i <= 100; i++) f[i].reset();
    f[a[u]][a[u]] = 1;
    for(auto v:g[u]) {
        for(int i = 1; i <= 100; i++) f[i] |= dp[v][i];
    }
    for(int i = 1; i <= 100; i++) 
        for(int j = i; j <= 100; j++) 
            if(f[i][j]) f[i] |= f[j + 1];
    dp[u][a[u]][a[u]] = 1;
    for(int i = 1; i <= 100; i++) 
        for(int j = i; j <= 100; j++) {
            if(i == a[u] && f[i + 1][j]) dp[u][i][j] = 1;
            if(j == a[u] && f[i][j - 1]) dp[u][i][j] = 1;
            if(f[i][a[u] - 1] && f[a[u] + 1][j]) dp[u][i][j] = 1;
        } 
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

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

    dfs(1);
    int ans = 0;
    for(int i = 1; i <= 100; i++) ans += dp[1][i].count();
    cout<<ans;
    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 1 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 3 ms 700 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 123 ms 17500 KB Output is correct
12 Correct 125 ms 17564 KB Output is correct
13 Correct 120 ms 17612 KB Output is correct
14 Correct 122 ms 18528 KB Output is correct
15 Correct 121 ms 18612 KB Output is correct
16 Correct 125 ms 18640 KB Output is correct
17 Correct 122 ms 17540 KB Output is correct
18 Correct 123 ms 17520 KB Output is correct
19 Correct 121 ms 17512 KB Output is correct
20 Correct 127 ms 17452 KB Output is correct