oj.uz

Submission #255419

# Submission time Handle Problem Language Result Execution time Memory
255419 2020-07-31T23:56:21 Z aZvezda Uzastopni (COCI15_uzastopni) C++14
0 / 160
 11 ms 7168 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;
bitset<MAX_VAL> dp[MAX_N][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

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 2 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 2 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 2 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 2 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 2 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 3 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 2 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 2 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 2 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 5 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 6 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 5 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 11 ms 7168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 9 ms 7168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 10 ms 7168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 6 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 5 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 5 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 5 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)