oj.uz

Submission #648741

# Submission time Handle Problem Language Result Execution time Memory
648741 2022-10-07T23:09:48 Z Adominator Uzastopni (COCI15_uzastopni) C++17
160 / 160
 111 ms 23796 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define ar array
#define vo vector
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()

#define rep(i, a, b) for(ll i=(a); i<(b); i++)
#define repd(i, a, b) for(ll i=(a); i>=(b); i--)

const int mxn=1e4+1, mxv=101;
vo<int> al[mxn], it[mxv];
bitset<mxv> memo[mxn][mxv];
vo<ar<int, 2>> itv[mxn];
int n, A[mxn];

void dp(int v) {
    for(auto i: al[v])
        dp(i);

    rep(i, 0, mxv)
        it[i].clear();

    for(auto i: al[v])
        for(auto [a, b]: itv[i])
            it[a].pb(b);

    repd(i, mxv-1, 1) {
        if(A[v]==i) {
            memo[v][i]|=memo[v][i+1];
            memo[v][i][i]=1;
        }
        else {
            for(auto j: it[i])
                if(j<A[v]||i>A[v]) {
                    memo[v][i]|=memo[v][j+1];
                    memo[v][i][j]=1;
                }
        }

        repd(j, mxv-1, i)
            if(memo[v][i][j]&&A[v]>=i&&A[v]<=j)
                itv[v].pb({i, j});
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;

    rep(i, 0, n)
        cin >> A[i];

    rep(i, 0, n-1) {
        int a, b;
        cin >> a >> b, --a, --b;

        al[a].pb(b);
    }

    dp(0);

    cout << sz(itv[0]);
}

Compilation message

uzastopni.cpp: In function 'void dp(int)':
uzastopni.cpp:46:28: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   46 |                 itv[v].pb({i, j});
      |                            ^
uzastopni.cpp:46:31: warning: narrowing conversion of 'j' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   46 |                 itv[v].pb({i, j});
      |                               ^

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 2 ms 936 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 2 ms 932 KB Output is correct
9 Correct 2 ms 880 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 84 ms 17228 KB Output is correct
12 Correct 81 ms 17232 KB Output is correct
13 Correct 79 ms 17228 KB Output is correct
14 Correct 93 ms 23744 KB Output is correct
15 Correct 93 ms 23748 KB Output is correct
16 Correct 111 ms 23796 KB Output is correct
17 Correct 86 ms 17164 KB Output is correct
18 Correct 83 ms 17160 KB Output is correct
19 Correct 96 ms 19592 KB Output is correct
20 Correct 95 ms 19532 KB Output is correct