oj.uz

Submission #465377

# Submission time Handle Problem Language Result Execution time Memory
465377 2021-08-15T19:08:28 Z JovanB Uzastopni (COCI15_uzastopni) C++17
160 / 160
 9 ms 4812 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 10000;

bool L[N+5][105], R[N+5][105];
int val[N+5];
vector <int> graf[N+5];

void dfs(int v){
    vector <int> vl, vr;
    L[v][val[v]] = R[v][val[v]] = 1;
    for(auto c : graf[v]){
        dfs(c);
        if(val[c] < val[v]) vl.push_back(c);
        else if(val[c] > val[v]) vr.push_back(c);
    }
    sort(vl.begin(), vl.end(), [](int a, int b){ return val[a] > val[b]; });
    sort(vr.begin(), vr.end(), [](int a, int b){ return val[a] < val[b]; });
    for(auto c : vl) for(int l=val[c]; l>=1; l--) for(int r=val[c]; r<val[v]; r++) L[v][l] |= L[v][r+1] & L[c][l] & R[c][r];
    for(auto c : vr) for(int l=val[v]+1; l<=val[c]; l++) for(int r=val[c]; r<=100; r++) R[v][r] |= R[v][l-1] & L[c][l] & R[c][r];
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    for(int i=1; i<=n; i++) cin >> val[i];
    for(int i=1; i<n; i++){
        int a, b;
        cin >> a >> b;
        graf[a].push_back(b);
    }
    dfs(1);
    int res = 0;
    for(int i=1; i<=val[1]; i++) for(int j=val[1]; j<=100; j++) res += (L[1][i] & R[1][j]);
    cout << res << "\n";
    return 0;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 560 KB Output is correct
5 Correct 1 ms 556 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 9 ms 2892 KB Output is correct
12 Correct 7 ms 2892 KB Output is correct
13 Correct 7 ms 2840 KB Output is correct
14 Correct 7 ms 4812 KB Output is correct
15 Correct 7 ms 4812 KB Output is correct
16 Correct 7 ms 4736 KB Output is correct
17 Correct 7 ms 2876 KB Output is correct
18 Correct 7 ms 2928 KB Output is correct
19 Correct 9 ms 2732 KB Output is correct
20 Correct 9 ms 2764 KB Output is correct