Submission #675176

#TimeUsernameProblemLanguageResultExecution timeMemory
675176vjudge1Uzastopni (COCI15_uzastopni)C++14
160 / 160
124 ms24412 KiB
#include <bits/stdc++.h> #define ii pair<int,int> #define fi first #define se second using namespace std; int n, v[10005]; vector<int> V[10005],q[105]; vector<ii> s[10005]; bitset<105> f[10005][105]; void Dfs(int x) { for(int y : V[x]) Dfs(y); for(int i = 0; i <= 100; i++) q[i].clear(); for(int y : V[x]) { for(ii it : s[y]) q[it.fi].push_back(it.se); } for(int l = 100; l >= 1; l--) { if (l == v[x]) { f[x][l] |= f[x][l + 1]; f[x][l].set(l); } else { for(int r : q[l]) if (r < v[x] || l > v[x]) { f[x][l] |= f[x][r + 1]; f[x][l].set(r); } } for(int r = 100; r >= l; r--) if(f[x][l][r] && v[x] >= l && v[x] <= r) s[x].push_back({l, r}); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 0; i < n; i++) cin >> v[i]; for(int i = 1; i < n; i++) { int a,b; cin >> a >> b; a--; b--; V[a].push_back(b); } Dfs(0); cout << s[0].size(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...