oj.uz

Submission #236007

# Submission time Handle Problem Language Result Execution time Memory
236007 2020-05-30T18:28:51 Z ant101 Uzastopni (COCI15_uzastopni) C++14
80 / 160
 37 ms 5888 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[101];
vector<int> rrange[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[u-1]) {
        dfsleft(node, v);
    }
}

void dfsright(int node, int u) {
    en[node].push_back(u);
    if (u >= 100) {
        return;
    }
    for (auto v : rrange[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 i = 0; i<101; i++) {
        lrange[i].clear();
        rrange[i].clear();
    }
    for (int i = 0; i<adj[u].size(); i++) {
        int v = adj[u][i];
        if (v == p) {
            continue;
        }
        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[second].push_back(first);
                rrange[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:103:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i<adj[u].size(); i++) {
                     ~^~~~~~~~~~~~~~
uzastopni.cpp:108:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j<st[v].size(); j++) {
                         ~^~~~~~~~~~~~~
uzastopni.cpp:109:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k = 0; k<en[v].size(); k++) {
                             ~^~~~~~~~~~~~~

Subtask #1
80.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1024 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Incorrect 5 ms 1024 KB Output isn't correct
4 Incorrect 5 ms 1024 KB Output isn't correct
5 Incorrect 5 ms 1152 KB Output isn't correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 5 ms 1024 KB Output is correct
8 Correct 5 ms 1152 KB Output is correct
9 Correct 5 ms 1152 KB Output is correct
10 Correct 5 ms 1152 KB Output is correct
11 Incorrect 12 ms 2048 KB Output isn't correct
12 Incorrect 12 ms 2048 KB Output isn't correct
13 Incorrect 13 ms 2048 KB Output isn't correct
14 Incorrect 28 ms 5880 KB Output isn't correct
15 Correct 37 ms 5752 KB Output is correct
16 Incorrect 28 ms 5888 KB Output isn't correct
17 Incorrect 12 ms 2048 KB Output isn't correct
18 Incorrect 12 ms 2048 KB Output isn't correct
19 Correct 15 ms 2304 KB Output is correct
20 Correct 14 ms 2304 KB Output is correct