oj.uz

Submission #236006

# Submission time Handle Problem Language Result Execution time Memory
236006 2020-05-30T18:18:26 Z ant101 Uzastopni (COCI15_uzastopni) C++14
0 / 160
 72 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


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

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

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


const int MAXN = 10010;

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


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

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


void f(int u, int p) {
    for (int i = 0; i<adj[u].size(); i++) {
        int v = adj[u][i];
        if (v == p) {
            continue;
        }
        f(v, u);
        for (int j = 0; j<st[v].size(); j++) {
            for (int k = 0; k<en[v].size(); k++) {
                int 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 >> N;
    for (int i = 1; i<=N; i++) {
        cin >> V[i];
    }
    for (int i = 0; i<N-1; i++) {
        int 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(int, int)':
uzastopni.cpp:92:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i<adj[u].size(); i++) {
                     ~^~~~~~~~~~~~~~
uzastopni.cpp:98:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j<st[v].size(); j++) {
                         ~^~~~~~~~~~~~~
uzastopni.cpp:99:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k = 0; k<en[v].size(); k++) {
                             ~^~~~~~~~~~~~~

Subtask #1
0 / 160.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 48512 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Runtime error 34 ms 48504 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
3 Runtime error 32 ms 48512 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
4 Runtime error 33 ms 48512 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
5 Runtime error 32 ms 48512 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
6 Runtime error 32 ms 48640 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
7 Runtime error 34 ms 48632 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
8 Runtime error 32 ms 48564 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
9 Runtime error 34 ms 48512 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
10 Runtime error 34 ms 48512 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
11 Runtime error 46 ms 50296 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
12 Runtime error 44 ms 50200 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
13 Runtime error 46 ms 50176 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
14 Runtime error 67 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 72 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 68 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 46 ms 50144 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
18 Runtime error 46 ms 50176 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
19 Runtime error 55 ms 52856 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
20 Runtime error 46 ms 52856 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)