oj.uz

답안 #675099

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
675099 2022-12-27T01:54:05 Z vjudge1 Uzastopni (COCI15_uzastopni) C++17
80 / 160
 74 ms 65536 KB 
#include <iostream>
#include <vector>
#include <algorithm>

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

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

void DFS(int u, int p) {
    for(int v : adj[u]) {
        if(v == p) continue;
        DFS(v, u);
    }
    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) 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) 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);
    DFS(1, 0);
    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

# 결과 실행 시간 메모리 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 824 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 1 ms 1212 KB Output is correct
10 Correct 1 ms 1236 KB Output is correct
11 Runtime error 58 ms 49012 KB Memory limit exceeded
12 Runtime error 53 ms 46504 KB Memory limit exceeded
13 Runtime error 51 ms 44516 KB Memory limit exceeded
14 Runtime error 74 ms 65536 KB Execution killed with signal 9
15 Runtime error 61 ms 65536 KB Execution killed with signal 9
16 Runtime error 62 ms 65536 KB Execution killed with signal 9
17 Runtime error 57 ms 44632 KB Memory limit exceeded
18 Runtime error 65 ms 44620 KB Memory limit exceeded
19 Runtime error 57 ms 65536 KB Execution killed with signal 9
20 Runtime error 57 ms 65536 KB Execution killed with signal 9