oj.uz

Submission #255423

# Submission time Handle Problem Language Result Execution time Memory
255423 2020-08-01T00:14:57 Z aZvezda Uzastopni (COCI15_uzastopni) C++14
16 / 160
 13 ms 7584 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;
vector<pair<short, short> > dp[MAX_N];
vector<int> g[MAX_N];
int arr[MAX_N];
vector<short> fake[MAX_VAL];
bool used[MAX_VAL];

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(auto &inter : dp[it]) {
            int i = inter.first;
            int j = inter.second;
            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);
            }
        }
        dp[it].resize(0);
    }
    for(int i = 0; i < MAX_VAL; i ++) {
        sort(fake[i].begin(), fake[i].end());
        fake[i].resize(unique(fake[i].begin(), fake[i].end()) - fake[i].begin());
        used[i] = false;
    }
    vector<int> foundl, foundr;
    queue<short> q;
    q.push(arr[x] - 1);
    q.push(arr[x] + 1);
    used[arr[x] + 1] = true;
    used[arr[x] - 1] = true;
    foundl.push_back(arr[x] - 1);
    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].push_back({l + 1, r - 1});
        }
    }
}

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);
    cout << dp[1].size() << endl;
    return 0;
}

Subtask #1
16.0 / 160.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 768 KB Output isn't correct
2 Runtime error 2 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 2 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 2 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 2 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 3 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 2 ms 1536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 2 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 1 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 2 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 5 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 5 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 5 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 11 ms 7584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 13 ms 7580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 10 ms 7552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 5 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 8 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Correct 13 ms 3072 KB Output is correct
20 Correct 12 ms 2688 KB Output is correct