# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
367506 | cpp219 | Uzastopni (COCI15_uzastopni) | C++14 | 343 ms | 65540 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.
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e4 + 9;
const ll inf = 1e9 + 7;
typedef pair<int,int> LL;
vector<ll> g[N];
ll n,v[N],x,y;
bitset<110> flag[N][110];
vector<LL> s[N];
void DFS(ll u){
for (auto i : g[u]) DFS(i); vector<ll> q[N];
for (auto i : g[u]){
for (auto j : s[i]) q[j.fs].push_back(j.sc);
}
for (ll l = 109;l > 0;l--){
if (l == v[u]){
flag[u][l] |= flag[u][l + 1]; flag[u][l].set(l);
}
else{
for (auto i : q[l]){
if (l > v[u] || i < v[u]){
flag[u][l] |= flag[u][i + 1]; flag[u][l].set(i);
}
}
}
for (ll i = 100;i >= l;i--) if (flag[u][l][i] == 1 && l <= v[u] && i >= v[u]) s[u].push_back({l,i});
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "tst"
if (fopen(task".INP","r")){
freopen(task".INP","r",stdin);
//freopen(task".OUT","w",stdout);
}
cin>>n;
for (ll i = 1;i <= n;i++) cin>>v[i];
for (ll i = 1;i < n;i++) cin>>x>>y,g[x].push_back(y);
DFS(1); cout<<s[1].size();
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |