oj.uz

Submission #59345

# Submission time Handle Problem Language Result Execution time Memory
59345 2018-07-21T15:33:42 Z Benq Uzastopni (COCI15_uzastopni) C++14
160 / 160
 21 ms 2196 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 10001;

int N, V[MX];
vi child[MX];
bitset<101> lo[MX], hi[MX];
bitset<101> oklo[101], okhi[101];

void solve(int x) {
    lo[x][V[x]] = hi[x][V[x]] = 1;
    for (int i: child[x]) solve(i);
    
    FOR(i,1,101) oklo[i].reset(), okhi[i].reset();
    for (int i: child[x]) 
        FOR(a,1,101) if (lo[i][a]) FOR(b,1,101) if (hi[i][b]) {
            if (V[x] < a) okhi[a][b] = 1;
            if (b < V[x]) oklo[b][a] = 1;
        }
    
    FORd(i,2,V[x]+1) if (lo[x][i]) lo[x] |= oklo[i-1];
    FOR(i,V[x],100) if (hi[x][i]) hi[x] |= okhi[i+1];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    FOR(i,1,N+1) cin >> V[i];
    F0R(i,N-1) {
        int a,b; cin >> a >> b;
        child[a].pb(b);
    }
    solve(1);
    cout << lo[1].count()*hi[1].count();
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 4 ms 612 KB Output is correct
3 Correct 4 ms 648 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 2 ms 800 KB Output is correct
6 Correct 3 ms 800 KB Output is correct
7 Correct 3 ms 800 KB Output is correct
8 Correct 3 ms 804 KB Output is correct
9 Correct 3 ms 928 KB Output is correct
10 Correct 3 ms 928 KB Output is correct
11 Correct 18 ms 1212 KB Output is correct
12 Correct 16 ms 1596 KB Output is correct
13 Correct 16 ms 1596 KB Output is correct
14 Correct 19 ms 2172 KB Output is correct
15 Correct 18 ms 2172 KB Output is correct
16 Correct 21 ms 2196 KB Output is correct
17 Correct 18 ms 2196 KB Output is correct
18 Correct 19 ms 2196 KB Output is correct
19 Correct 13 ms 2196 KB Output is correct
20 Correct 16 ms 2196 KB Output is correct