Submission #300086

#TimeUsernameProblemLanguageResultExecution timeMemory
300086HynDufUzastopni (COCI15_uzastopni)C++11
160 / 160
6 ms1408 KiB
#include <bits/stdc++.h> #define task "U" #define all(v) (v).begin(), (v).end() #define rep(i, l, r) for (int i = (l); i <= (r); ++i) #define Rep(i, r, l) for (int i = (r); i >= (l); --i) #define DB(X) { cerr << #X << " = " << (X) << '\n'; } #define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; } #define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; } #define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; } #define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';} #define SZ(x) ((int)(x).size()) #define pb push_back #define eb emplace_back #define pf push_front #define F first #define S second #define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a)); #define next ___next #define prev ___prev #define y1 ___y1 #define left ___left #define right ___right #define y0 ___y0 #define div ___div #define j0 ___j0 #define jn ___jn using ll = long long; using ld = long double; using ull = unsigned long long; using namespace std; typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<ll> vl; const int N = 1e4 + 2, NN = 102; int n, val[N]; bool in[NN]; bitset<NN> l[N], r[N]; vi g[N]; void dfs(int u) { in[val[u]] = 1; for (int v : g[u]) if (!in[val[v]]) dfs(v); l[u][val[u]] = 1; r[u][val[u]] = 1; if (SZ(g[u])) sort(all(g[u]), [&](const int &A, const int &B) { return val[A] < val[B]; }); for (int v : g[u]) if (!in[val[v]] && val[v] > val[u]) { rep(i, val[u] + 1, val[v]) if (r[u][i - 1] && l[v][i]) { r[u] |= r[v]; break; } } if (SZ(g[u])) reverse(all(g[u])); for (int v : g[u]) if (!in[val[v]] && val[v] < val[u]) { rep(i, val[v], val[u] - 1) if (r[v][i] && l[u][i + 1]) { l[u] |= l[v]; break; } } in[val[u]] = 0; } int main() { #ifdef HynDuf freopen(task".in", "r", stdin); //freopen(task".out", "w", stdout); #else ios_base::sync_with_stdio(false); cin.tie(nullptr); #endif cin >> n; rep(i, 1, n) cin >> val[i]; rep(i, 2, n) { int u, v; cin >> u >> v; g[u].eb(v); g[v].eb(u); } dfs(1); cout << l[1].count() * r[1].count(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...