Submission #675162

#TimeUsernameProblemLanguageResultExecution timeMemory
675162vjudge1Uzastopni (COCI15_uzastopni)C++17
80 / 160
79 ms65536 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; const int maxn = 1e4 + 5; int n, a[maxn], p[maxn]; vector <int> adj[maxn]; bool f[maxn][105][105]; vector <int> vt; vector <pair <int, int>> d[maxn]; bool cmp(int i, int j) { return a[i] < a[j]; } void DFS1(int u) { vt.push_back(u); for(int v : adj[u]) { if(v == p[u]) continue; p[v] = u; DFS1(v); } } //void solve() { // for(int id = int(vt.size() - 1); id >= 0; --id) { // int u = vt[id]; // int d = lower_bound(adj[u].begin(), adj[u].end(), u, cmp) - adj[u].begin(); // f[u][a[u]][a[u]] = 1; // for(int i = d - 1; i >= 0; --i) { // int v = adj[u][i]; // if(v == p[u]) continue; // // for(int j = 1; j < a[u]; ++j) { // for(int j1 = j; j1 < a[u]; ++j1) f[u][j][a[u]] |= (f[u][j1 + 1][a[u]] & f[v][j][j1]); // } // } // for(int i = d; i < int(adj[u].size()); ++i) { // int v = adj[u][i]; // if(v == p[u]) continue; // for(int j = a[u] + 1; j <= 100; ++j) { // for(int j1 = j; j1 <= 100; ++j1) f[u][a[u]][j1] |= (f[u][a[u]][j - 1] & f[v][j][j1]); // } // } // for(int i = 1; i <= a[u]; ++i) { // for(int j = a[u]; j <= 100; ++j) f[u][i][j] |= (f[u][i][a[u]] & f[u][a[u]][j]); // } // } //} int main() { ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cin >> n; for(int i = 1; i <= n; ++i) cin >> a[i]; for(int i = 1; i < n; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } for(int i = 1; i <= n; ++i) sort(adj[i].begin(), adj[i].end(), cmp); DFS1(1); for(int id = int(vt.size()) - 1; id >= 0; --id) { int u = vt[id]; int d = lower_bound(adj[u].begin(), adj[u].end(), u, cmp) - adj[u].begin(); f[u][a[u]][a[u]] = 1; for(int i = d - 1; i >= 0; --i) { int v = adj[u][i]; if(v == p[u]) continue; for(int j = 1; j < a[u]; ++j) { for(int j1 = j; j1 < a[u]; ++j1) f[u][j][a[u]] |= (f[u][j1 + 1][a[u]] & f[v][j][j1]); } } for(int i = d; i < int(adj[u].size()); ++i) { int v = adj[u][i]; if(v == p[u]) continue; for(int j = a[u] + 1; j <= 100; ++j) { if(!f[u][a[u]][j - 1]) continue; for(int j1 = j; j1 <= 100; ++j1) f[u][a[u]][j1] |= (f[u][a[u]][j - 1] & f[v][j][j1]); } } for(int i = 1; i <= a[u]; ++i) { for(int j = a[u]; j <= 100; ++j) f[u][i][j] |= (f[u][i][a[u]] & f[u][a[u]][j]); } } int res =0 ; for(int i = 1; i <= 100; ++i) { for(int j = i; j <= 100; ++j) { if(f[1][i][j]) ++res; } } cout << res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...