Submission #1274438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274438		duongquanghai08	Uzastopni (COCI15_uzastopni)	C++20	152 / 160	4 ms	1864 KiB

uzastopni

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10000 + 5;
// Dùng 105 để an toàn truy cập chỉ số 0 và 101 trong các điều kiện biên.
const int MAXV = 105; // giá trị V_i ∈ [1..100]

int n;
int a[MAXN];
vector<int> adj[MAXN];
bitset<MAXV> dp[MAXN];

bool cmp_by_value(int u, int v) { return a[u] < a[v]; }

void calc_dp(int u) {
    for (int v : adj[u]) calc_dp(v);

    dp[u].reset();
    dp[u][a[u]] = 1;

    // Xử lý phía "lớn hơn" a[u] để tạo các đoạn [a[u]..j]
    sort(adj[u].begin(), adj[u].end(), cmp_by_value);
    int j = a[u] + 1;
    for (int v : adj[u]) {
        if (a[v] <= a[u]) continue;
        if (dp[v][j]) {
            j = max(j, a[v]);
            while (j <= 100 && dp[v][j]) {
                dp[u][j] = 1;
                ++j;
            }
        }
    }

    // Xử lý phía "nhỏ hơn" a[u] để tạo các đoạn [j..a[u]]
    reverse(adj[u].begin(), adj[u].end());
    j = a[u] - 1;
    for (int v : adj[u]) {
        if (a[v] >= a[u]) continue;
        if (dp[v][j]) {
            j = min(j, a[v]);
            while (j >= 1 && dp[v][j]) {
                dp[u][j] = 1;
                --j;
            }
        }
    }
}

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

    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 2; i <= n; ++i) {
        int u, v; 
        cin >> u >> v;      // u is direct superior of v
        adj[u].push_back(v);
    }

    calc_dp(1);

    long long L = 0, R = 0;
    for (int i = 1; i <= a[1]; ++i) if (dp[1][i]) ++L;      // số j tạo [j..a[1]]
    for (int i = a[1]; i <= 100; ++i) if (dp[1][i]) ++R;    // số j tạo [a[1]..j]

    cout << (L * R) << '\n';
    return 0;
}

• Subtask 1: 152 / 160