# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
141436 | meatrow | Uzastopni (COCI15_uzastopni) | C++17 | 8 ms | 1460 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e4 + 5;
const int M = 101;
int jojoke[N];
int l[N], r[N];
vector<int> g[N];
int a[M];
pair<int, int> p[N * 2];
void dfs(int v) {
l[v] = r[v] = jojoke[v];
for (int u : g[v]) {
dfs(u);
}
fill(a, a + M, 0);
int sz = 0;
for (int u : g[v]) {
if (l[u] <= jojoke[v] && jojoke[v] <= r[u]) {
if (jojoke[u] < jojoke[v]) {
p[sz++] = { l[u], 1 };
p[sz++] = { jojoke[v] + 1, -1 };
}
if (jojoke[u] > jojoke[v]) {
p[sz++] = { jojoke[v], 1 };
p[sz++] = { r[u] + 1, -1 };
}
} else {
p[sz++] = { l[u], 1 };
p[sz++] = { r[u] + 1, -1 };
}
}
sort(p, p + sz);
int b = 0;
for (int i = 0; i < sz; i++) {
b += p[i].second;
if (b > 0) {
for (int j = p[i].first; j < p[i + 1].first; j++) {
a[j] = 1;
}
}
}
for (int i = jojoke[v] + 1; i < M; i++) {
if (a[i] == 0) {
break;
}
r[v] = i;
}
for (int i = jojoke[v] - 1; i > 0; i--) {
if (a[i] == 0) {
break;
}
l[v] = i;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> jojoke[i];
}
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
}
dfs(1);
cout << (jojoke[1] - l[1] + 1) * (r[1] - jojoke[1] + 1) << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |