oj.uz

Submission #675105

# Submission time Handle Problem Language Result Execution time Memory
675105 2022-12-27T01:58:31 Z vjudge1 Uzastopni (COCI15_uzastopni) C++17
80 / 160
 63 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][105][105];
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 2 ms 980 KB Output is correct
6 Correct 2 ms 1364 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 2 ms 1364 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 1 ms 1236 KB Output is correct
11 Runtime error 57 ms 49288 KB Memory limit exceeded
12 Runtime error 55 ms 46764 KB Memory limit exceeded
13 Runtime error 63 ms 44824 KB Memory limit exceeded
14 Runtime error 60 ms 65536 KB Execution killed with signal 9
15 Runtime error 56 ms 65536 KB Execution killed with signal 9
16 Runtime error 63 ms 65536 KB Execution killed with signal 9
17 Runtime error 53 ms 44792 KB Memory limit exceeded
18 Runtime error 52 ms 44716 KB Memory limit exceeded
19 Runtime error 62 ms 65536 KB Execution killed with signal 9
20 Runtime error 60 ms 65536 KB Execution killed with signal 9