oj.uz

Submission #236004

# Submission time Handle Problem Language Result Execution time Memory
236004 2020-05-30T18:16:59 Z ant101 Uzastopni (COCI15_uzastopni) C++14
0 / 160
 73 ms 65540 KB 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
using namespace std;

//#define RDEBUG 1
#ifdef RDEBUG
#define D(x) x
#else
#define D(x)
#endif
#define inf 0x7fffffff
#define MOD 1000000007

typedef long long ll;


ll add(ll a, ll b) {
    a += b;
    if(a >= MOD) {
        a -= MOD;
    }
    return a;
}
ll sub(ll a, ll b) {
    a -= b;
    if(a < 0) {
        a += MOD;
    }
    return a;
}

ll mul(ll a, ll b) {
    return (a * b)%MOD;
}

void add_self(ll& a, ll b) {
    a = add(a, b);
}
void sub_self(ll& a, ll b) {
    a = sub(a, b);
}
void mul_self(ll& a, ll b) {
    a = mul(a, b);
}


const ll MAXN = 10010;

ll N;
ll V[MAXN];
vector<ll> adj[MAXN];
vector<ll> lrange[MAXN][101];
vector<ll> rrange[MAXN][101];
vector<ll> st[MAXN];
vector<ll> en[MAXN];


void dfsleft(ll node, ll u) {
    st[node].push_back(u);
    if (u <= 1) {
        return;
    }
    for (auto v : lrange[node][u-1]) {
        dfsleft(node, v);
    }
}

void dfsright(ll node, ll u) {
    en[node].push_back(u);
    if (u >= 100) {
        return;
    }
    for (auto v : rrange[node][u+1]) {
        dfsright(node, v);
    }
}


void f(ll u, ll p) {
    for (ll i = 0; i<adj[u].size(); i++) {
        ll v = adj[u][i];
        if (v == p) {
            continue;
        }
        f(v, u);
        for (ll j = 0; j<st[v].size(); j++) {
            for (ll k = 0; k<en[v].size(); k++) {
                ll first = st[v][j], second = en[v][k];
                if (first > second) {
                    continue;
                }
                lrange[u][second].push_back(first);
                rrange[u][first].push_back(second);
            }
        }
    }
    dfsleft(u, V[u]);
    dfsright(u, V[u]);
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for (ll i = 1; i<=N; i++) {
        cin >> V[i];
    }
    for (ll i = 0; i<N-1; i++) {
        ll a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        
    }
    f(1, -1);
    cout << st[1].size()*en[1].size() << "\n";
    return 0;
}

Compilation message

uzastopni.cpp: In function 'void f(ll, ll)':
uzastopni.cpp:94:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (ll i = 0; i<adj[u].size(); i++) {
                    ~^~~~~~~~~~~~~~
uzastopni.cpp:100:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (ll j = 0; j<st[v].size(); j++) {
                        ~^~~~~~~~~~~~~
uzastopni.cpp:101:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (ll k = 0; k<en[v].size(); k++) {
                            ~^~~~~~~~~~~~~

Subtask #1
0 / 160.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 48632 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Runtime error 33 ms 48512 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
3 Runtime error 34 ms 48512 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
4 Runtime error 35 ms 48512 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
5 Runtime error 34 ms 48508 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
6 Runtime error 34 ms 48640 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
7 Runtime error 35 ms 48640 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
8 Runtime error 33 ms 48640 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
9 Runtime error 33 ms 48512 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
10 Runtime error 33 ms 48512 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
11 Runtime error 44 ms 50296 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
12 Runtime error 44 ms 50424 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
13 Runtime error 45 ms 50552 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
14 Runtime error 65 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 73 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 67 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 46 ms 50552 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
18 Runtime error 46 ms 50552 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
19 Runtime error 50 ms 55416 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
20 Runtime error 50 ms 55800 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)