oj.uz

답안 #255418

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
255418 2020-07-31T23:55:50 Z aZvezda Uzastopni (COCI15_uzastopni) C++14
0 / 160
 15 ms 7552 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl

const int MAX_N = 1e4 + 10, MAX_VAL = 1e2 + 10;
bool dp[MAX_N][MAX_VAL][MAX_VAL];
int sz[MAX_N];
vector<int> g[MAX_N];
int arr[MAX_N];
vector<int> fake[MAX_VAL];
bool used[MAX_N];

void dfs(int x, int p) {
    for(auto it : g[x]) {
        if(it == p) {continue;}
        dfs(it, x);
    }
    for(int i = 0; i < MAX_VAL; i ++) {
        fake[i].resize(0);
    }
    for(auto it : g[x]) {
        if(it == p) {continue;}
        for(int i = 0; i < MAX_VAL; i ++) {
            for(int j = i; j < MAX_VAL; j ++) if(dp[it][i][j]) {
                if(i <= arr[x] && j >= arr[x]) {continue;}
                if(i == arr[x] || j == arr[x]) {continue;}
                if(i < arr[x]) {
                    fake[j].push_back(i - 1);
                } else {
                    fake[i].push_back(j + 1);
                }
            }
        }
    }
    for(int i = 0; i < MAX_VAL; i ++) {
        used[i] = false;
    }
    vector<int> foundl, foundr;
    queue<int> q;
    q.push(arr[x] - 1);
    q.push(arr[x] + 1);
    used[arr[x] - 1] = true;
    foundl.push_back(arr[x] - 1);
    used[arr[x] + 1] = true;
    foundr.push_back(arr[x] + 1);
    while(q.front()) {
        auto curr = q.front(); q.pop();
        for(auto it : fake[curr]) {
            if(!used[it]) {
                used[it] = true;
                if(it < arr[x]) {
                    foundl.push_back(it);
                } else {
                    foundr.push_back(it);
                }
                q.push(it);
            }
        }
    }

    for(auto l : foundl) {
        for(auto r : foundr) {
            dp[x][l + 1][r - 1] = true;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> arr[i];
    }
    for(int i = 0; i < n - 1; i ++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, 0);
    int ans = 0;
    for(int i = 0; i < MAX_VAL; i ++) {
        for(int j = 0; j < MAX_VAL; j ++) {
            ans += dp[1][i][j];
        }
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 6 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 6 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 6 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 6 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 6 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 6 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 6 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 6 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 6 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 10 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 9 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 9 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 15 ms 7552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 14 ms 7424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 14 ms 7296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 9 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 10 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 9 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 9 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)