제출 #98657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98657		minhtung0404	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	23 ms	3712 KiB

uzastopni

//https://oj.uz/problem/view/COCI15_uzastopni

#include<bits/stdc++.h>
const int N = 1e4 + 5;
using namespace std;

vector <int> G[N];
int n, a[N];
bool ck[2][N], l[N][100], r[N][100];

void dfs(int u){
    for (auto v : G[u]) dfs(v);
    l[u][a[u]] = r[u][a[u]] = true;
    for (int i = a[u]; i > 0; i--) if (l[u][i]){
        for (auto v : G[u]) if (!ck[0][v] && r[v][i-1]) {
            ck[0][v] = true;
            for (int i = 0; i < 100; i++) l[u][i] = max(l[u][i], l[v][i]);
        }
    }
    for (int i = a[u]; i < 99; i++) if (r[u][i]){
        for (auto v : G[u]) if (!ck[1][v] && l[v][i+1]) {
            ck[1][v] = true;
            for (int i = 0; i < 100; i++) r[u][i] = max(r[u][i], r[v][i]);
        }
    }
//    cout << u << "\n";
//    for (int i = 0; i < 100; i++) if (l[u][i]) cout << i << " "; cout << "\n";
//    for (int i = 0; i < 100; i++) if (r[u][i]) cout << i << " "; cout << "\n";
//    cout << "\n";
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], a[i]--;
    for (int i = 2; i <= n; i++){
        int u, v; cin >> u >> v;
        G[u].push_back(v);
    }
    dfs(1);
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < 100; i++) if (l[1][i]) cnt1++;
    for (int i = 0; i < 100; i++) if (r[1][i]) cnt2++;
    cout << cnt1 * cnt2;
}

• Subtask 1: 160 / 160