# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
331458 | BeanZ | Uzastopni (COCI15_uzastopni) | C++14 | 95 ms | 29992 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.
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1e4 + 5;
const int mod = 1e9 + 7;
const int lim = 100;
bitset<101> bit[N][105];
vector<ll> node[N], d[101];
vector<pair<ll, ll>> q[N];
ll a[N];
/*
Sol: Goi q[u] la tat ca cac cap (l, r) sao cho subtree cua u co the lam dc 1 doan (l, r)
Goi bit[u][l] la mot mang bool neu bit thu r cua mang nay bat tuc la doan (l, r) trong subtree u co the lam dc
bit[u][l] dc tinh bang cach xet toan bo cac node con cua u
Ta se tinh dc q[u] cua tung node con cua u
Khi do ta xem tat ca cac cap (lf, rt) ma lf == l
{
bit[u][l] |= bit[u][r + 1] (de tranh bi lay 2 joke chung nen se lay bit tu r + 1 tro di)
bit[u][l].set(r) (tu cai dat cho no rang (l, r) dc)
}
Sau do voi moi doan (l, r) dc tao thanh ta kiem tra xem l <= a[u] && r >= a[u] ko roi them no vao q[u]
de tinh cho cha cua u.
*/
void dfs(ll u){
for (auto j : node[u]) dfs(j);
for (int i = 1; i <= lim; i++) d[i].clear();
for (auto j : node[u]){
for (auto t : q[j]){
d[t.first].push_back(t.second);
}
}
for (int i = lim; i >= 1; i--){
if (a[u] == i){
bit[u][i].set(i);
bit[u][i] |= bit[u][i + 1];
} else {
for (auto r : d[i]){
if (r < a[u] || i > a[u]){
bit[u][i].set(r);
bit[u][i] |= bit[u][r + 1];
}
}
}
for (int r = lim; r >= i; r--){
if (bit[u][i][r] && a[u] >= i && a[u] <= r){
q[u].push_back({i, r});
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("A.inp", "r")){
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ll n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i < n; i++){
ll u, v;
cin >> u >> v;
node[u].push_back(v);
}
dfs(1);
cout << q[1].size();
}
/*
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |