Submission #1274425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274425		duongquanghai08	Uzastopni (COCI15_uzastopni)	C++20	104 / 160	12 ms	21312 KiB

uzastopni

#include <bits/stdc++.h>
using namespace std;
const int N = 7e4 + 1;
const int M = 2001;
int n, m;
int a[N];
vector<int> adj[N];
bool dp[N][M];
bool cmp(int u, int v) {
    return a[u] < a[v];
}
void calc_dp(int u) {
    sort(adj[u].begin(), adj[u].end(), cmp);
    for (int v : adj[u]) calc_dp(v);
    int j = a[u] + 1;
    dp[u][a[u]] = true;
    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] = true;
                j++;
            }
        }
    }

    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] = true;
                j--;
            }
        }
    }
}
void Solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 2; i <= n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
    }
    calc_dp(1);
    int l = 0, r = 0;
    for (int i = 1; i <= a[1]; i++) if(dp[1][i]) l++;
    for (int i = a[1]; i <= 100; i++) if(dp[1][i]) r++;

    cout << l * r;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
   // freopen("uzastopni.inp", "r", stdin);
    //freopen("uzastopni.out", "w", stdout);
    Solve();
}

• Subtask 1: 104 / 160