oj.uz

Submission #1108750

# Submission time Handle Problem Language Result Execution time Memory
1108750 2024-11-05T01:42:37 Z Drew_ Uzastopni (COCI15_uzastopni) C++17
80 / 160
 8 ms 4972 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const int MAXN = 1 << 14;
const int MAXK = 1 << 7;

int N, ar[MAXN];
vector<int> adj[MAXN];

bitset<MAXN> ok;
vector<int> ql[MAXK], qr[MAXK];
vector<int> ivl[MAXK], ivlR[MAXK];

void dfs(int node)
{
    for (int to : adj[node]) {
        dfs(to);
    }

    for (int i = 0; i < MAXK; ++i) {
        ivl[i].clear();
        ivlR[i].clear();
    }

    for (int to : adj[node]) {
        for (int l : ql[to]) {
            for (int r : qr[to]) {
                ivl[l].pb(r);
                ivlR[r].pb(l);
            }
        }
    }
    
    ok.reset();
    ok[ar[node]] = 1;
    // find suffix that ends with ar[node]-1
    for (int r = ar[node] - 1; r >= 0; --r) if (ok[r+1]) {
        for (int l : ivlR[r]) {
            ok[l] = 1;
        }
    }

    // find prefix that starts with ar[node]+1
    for (int l = ar[node] + 1; l < MAXK; ++l) if (ok[l-1]) {
        for (int r : ivl[l]) {
            ok[r] = 1;
        }
    }

    
    for (int i = 0; i <= ar[node]; ++i) if (ok[i]) {
        ql[node].pb(i);
    }
    for (int i = ar[node]; i < MAXK; ++i) if (ok[i]) {
        qr[node].pb(i);
    }
}

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

    cin >> N;
    for (int i = 1; i <= N; ++i) {
        cin >> ar[i];
    }
    for (int i = 0; i < N-1; ++i) {
        int u, v; cin >> u >> v;
        adj[u].pb(v);
    }

    dfs(1);

    cout << ql[1].size() * qr[1].size() << '\n';

    return 0;
}

Subtask #1
80.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 848 KB Output is correct
2 Correct 1 ms 848 KB Output is correct
3 Correct 1 ms 848 KB Output is correct
4 Correct 1 ms 848 KB Output is correct
5 Correct 1 ms 848 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 1 ms 848 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 1 ms 848 KB Output is correct
11 Runtime error 5 ms 1904 KB Execution killed with signal 6
12 Runtime error 6 ms 1872 KB Execution killed with signal 6
13 Runtime error 6 ms 1872 KB Execution killed with signal 6
14 Runtime error 8 ms 4972 KB Execution killed with signal 6
15 Runtime error 8 ms 4944 KB Execution killed with signal 6
16 Runtime error 8 ms 4944 KB Execution killed with signal 6
17 Runtime error 6 ms 1872 KB Execution killed with signal 6
18 Runtime error 5 ms 1872 KB Execution killed with signal 6
19 Runtime error 5 ms 1616 KB Execution killed with signal 6
20 Runtime error 5 ms 1872 KB Execution killed with signal 6