oj.uz

Submission #884711

# Submission time Handle Problem Language Result Execution time Memory
884711 2023-12-08T07:45:41 Z parlimoos Uzastopni (COCI15_uzastopni) C++17
160 / 160
 5 ms 3676 KB 
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define cl clear
#define bg begin
#define lb lower_bound
#define ub upper_bound
#define arr(x) array<int , x>
#define endl '\n'

int n;
int vs[10000];
vector<arr(2)> tr[10000];
bool ls[10000][100];
bool rs[10000][100];

void dfs(int v = 0){
    // cout << v << ">>\n" << flush;
    for(auto el : tr[v]) dfs(el[1]);
    ls[v][vs[v]] = 1 , rs[v][vs[v]] = 1;
    arr(2) d = {vs[v] , -1};
    int inx1 = int(lb(tr[v].bg() , tr[v].end() , d) - tr[v].bg());
    while(inx1 > 0){
        inx1--;
        bool flg = 0;
        for(int i = 99 ; i >= 1 ; i--){
            if(ls[v][i] and rs[tr[v][inx1][1]][i - 1]){
                flg = 1;
                break;
            }
        }
        if(flg) for(int i = 99 ; i >= 0 ; i--) if(ls[tr[v][inx1][1]][i]) ls[v][i] = 1;
    }
    d = {vs[v] , int(1e9)};
    int inx2 = int(ub(tr[v].bg() , tr[v].end() , d) - tr[v].bg());
    while(inx2 < (int)tr[v].size()){
        bool flg = 0;
        for(int i = 0 ; i < 99 ; i++){
            if(rs[v][i] and ls[tr[v][inx2][1]][i + 1]){
                flg = 1;
                break;
            }
        }
        if(flg) for(int i = 0 ; i <= 99 ; i++) if(rs[tr[v][inx2][1]][i]) rs[v][i] = 1;
        inx2++;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 0 ; i < n ; i++){
        cin >> vs[i];
        vs[i]--;
    }
    for(int i = 1 ; i < n ; i++){
        int a , b;
        cin >> a >> b;
        tr[a - 1].pb({vs[b - 1] , b - 1});
    }
    for(int i = 0 ; i < n ; i++) sort(tr[i].bg() , tr[i].end());
    dfs();
    int o1 = 0 , o2 = 0;
    for(int i = 0 ; i < 100 ; i++){
        if(ls[0][i] and i <= vs[0]) o1++;
        if(rs[0][i] and i >= vs[0]) o2++;
    }
    cout << o1 * o2;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2548 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 4 ms 2652 KB Output is correct
12 Correct 4 ms 2652 KB Output is correct
13 Correct 4 ms 2652 KB Output is correct
14 Correct 5 ms 3676 KB Output is correct
15 Correct 4 ms 3676 KB Output is correct
16 Correct 4 ms 3676 KB Output is correct
17 Correct 4 ms 2652 KB Output is correct
18 Correct 4 ms 2652 KB Output is correct
19 Correct 4 ms 2652 KB Output is correct
20 Correct 4 ms 2652 KB Output is correct