Submission #251836

#TimeUsernameProblemLanguageResultExecution timeMemory
251836VEGAnnUzastopni (COCI15_uzastopni)C++14
80 / 160
422 ms18296 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("unroll-loops") //#pragma GCC optimize("-O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("fast-math") //#pragma GCC optimize("no-stack-protector") #define sz(x) ((int)x.size()) #define i2 array<int,2> #define PB push_back using namespace std; typedef long long ll; const int N = 10010; const int V = 101; const int C = 22; const int md = 10007; vector<int> g[N]; bitset<V> f[N][V], lf[3][V], clr; int n, a[N]; void clear(int tp){ for (int i = 0; i < V; i++) lf[tp][i] = clr; } void dfs(int v, int p){ int lst = 0; for (int u : g[v]){ if (u == p) continue; dfs(u, v); } clear(0); lf[0][a[v]][a[v]] = 1; for (int u : g[v]){ if (u == p) continue; // cerr << lf[lst][1][3] << '\n'; lst ^= 1; clear(lst); for (int l = 1; l < V; l++) for (int r = l; r < V; r++) { if (f[u][l][r] && (l < a[v] || r > a[v])){ lf[lst][l][r] = 1; if (r + 1 < V) lf[lst][l] |= (lf[lst ^ 1][r + 1]); } if (lf[lst ^ 1][l][r]){ if (r + 1 < V) lf[lst][l] |= (f[u][r + 1]); } } clear(2); for (int r = 2; r < V; r++) for (int l = r - 1; l > 0; l--) { if (lf[lst][l][r - 1]) lf[2][l] |= lf[lst ^ 1][r]; if (lf[lst ^ 1][l][r]) lf[2][l] |= lf[lst][r]; //right too } for (int l = 1; l < V; l++) for (int r = l; r < V; r++){ bool res = bool(lf[2][l][r] || lf[lst ^ 1][l][r] || lf[lst][l][r]); lf[lst][l][r] = res; } } for (int l = 1; l <= a[v]; l++) for (int r = a[v]; r < V; r++) f[v][l][r] = lf[lst][l][r]; // if (v == 2) { // cerr << "ADSGDA " << f[v][3][4] << '\n'; // cerr << "ADSGDA " << f[v][3][3] << '\n'; //// cerr << "ADSGDA " << f[v][3][3] << '\n'; // } } int main() { #ifdef _LOCAL freopen("in.txt","r",stdin); // freopen("output.txt","w",stdout); #else // freopen("mining.in","r",stdin); freopen("mining.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); #endif cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 1; i < n; i++){ int x, y; cin >> x >> y; x--; y--; g[x].PB(y); g[y].PB(x); } dfs(0, -1); int ans = 0; for (int l = 1; l < V; l++) for (int r = l; r < V; r++) if (f[0][l][r]) { // cerr << l << " " << r << '\n'; ans++; } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...