Submission #648741

#	Time	Username	Problem	Language	Result	Execution time	Memory
648741		Adominator	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	111 ms	23796 KiB

uzastopni

#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 (stderr)

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 / 160