oj.uz

Submission #236008

# Submission time Handle Problem Language Result Execution time Memory
236008 2020-05-30T18:31:07 Z ant101 Uzastopni (COCI15_uzastopni) C++14
160 / 160
 145 ms 25976 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];
set<int> lrange[101];
set<int> rrange[101];
set<int> st[MAXN];
set<int> en[MAXN];


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

void dfsright(int node, int u) {
    en[node].insert(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 (auto first : st[v]) {
            for (auto second : en[v]) {
                if (first > second) {
                    continue;
                }
                lrange[second].insert(first);
                rrange[first].insert(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++) {
                     ~^~~~~~~~~~~~~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 5 ms 1536 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct
4 Correct 5 ms 1536 KB Output is correct
5 Correct 5 ms 1536 KB Output is correct
6 Correct 6 ms 1664 KB Output is correct
7 Correct 6 ms 1664 KB Output is correct
8 Correct 6 ms 1664 KB Output is correct
9 Correct 8 ms 1536 KB Output is correct
10 Correct 6 ms 1536 KB Output is correct
11 Correct 18 ms 2944 KB Output is correct
12 Correct 19 ms 2944 KB Output is correct
13 Correct 23 ms 3072 KB Output is correct
14 Correct 143 ms 25848 KB Output is correct
15 Correct 145 ms 25976 KB Output is correct
16 Correct 145 ms 25880 KB Output is correct
17 Correct 19 ms 2944 KB Output is correct
18 Correct 19 ms 2944 KB Output is correct
19 Correct 52 ms 3576 KB Output is correct
20 Correct 55 ms 3576 KB Output is correct