oj.uz

Submission #675102

# Submission time Handle Problem Language Result Execution time Memory
675102 2022-12-27T01:57:20 Z vjudge1 Uzastopni (COCI15_uzastopni) C++17
80 / 160
 83 ms 65536 KB 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int maxn = 1e4 + 5;
int n, a[maxn], p[maxn];
vector <int> adj[maxn];
bool f[maxn][101][101];
vector <int> vt;

bool cmp(int i, int j) {
    return a[i] < a[j];
}

void DFS1(int u) {
    vt.push_back(u);
    for(int v : adj[u]) {
        if(v == p[u]) continue;
        p[v] = u;
        DFS1(v);
    }
}

void solve() {
    for(int id = int(vt.size() - 1); id >= 0; --id) {
        int u = vt[id];
        int d = lower_bound(adj[u].begin(), adj[u].end(), u, cmp) - adj[u].begin();
        f[u][a[u]][a[u]] = 1;
        for(int i = d - 1; i >= 0; --i) {
            int v = adj[u][i];
            if(v == p[u]) continue;

            for(int j = 1; j < a[u]; ++j) {
                for(int j1 = j; j1 < a[u]; ++j1) f[u][j][a[u]] |= (f[u][j1 + 1][a[u]] & f[v][j][j1]);
            }
        }
        for(int i = d; i < int(adj[u].size()); ++i) {
            int v = adj[u][i];
            if(v == p[u]) continue;
            for(int j = a[u] + 1; j <= 100; ++j) {
                for(int j1 = j; j1 <= 100; ++j1) f[u][a[u]][j1] |= (f[u][a[u]][j - 1] & f[v][j][j1]);
            }
        }
        for(int i = 1; i <= a[u]; ++i) {
            for(int j = a[u]; j <= 100; ++j) f[u][i][j] |= (f[u][i][a[u]] & f[u][a[u]][j]);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL); cin.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1; i <= n; ++i) sort(adj[i].begin(), adj[i].end(), cmp);
    DFS1(1);
    solve();
    int res =0 ;
    for(int i = 1; i <= 100; ++i) {
        for(int j = i; j <= 100; ++j) {
            if(f[1][i][j]) ++res;
        }
    }
    cout << res;
    return 0;
}

Subtask #1
80.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 2 ms 1236 KB Output is correct
11 Runtime error 56 ms 49144 KB Memory limit exceeded
12 Runtime error 53 ms 46500 KB Memory limit exceeded
13 Runtime error 53 ms 44460 KB Memory limit exceeded
14 Runtime error 64 ms 65536 KB Execution killed with signal 9
15 Runtime error 67 ms 65536 KB Execution killed with signal 9
16 Runtime error 83 ms 65536 KB Execution killed with signal 9
17 Runtime error 64 ms 44620 KB Memory limit exceeded
18 Runtime error 52 ms 44596 KB Memory limit exceeded
19 Runtime error 61 ms 65536 KB Execution killed with signal 9
20 Runtime error 76 ms 65536 KB Execution killed with signal 9