Submission #644253

#TimeUsernameProblemLanguageResultExecution timeMemory
644253BackNoobUzastopni (COCI15_uzastopni)C++14
160 / 160
221 ms18808 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define endl '\n' #define MASK(i) (1LL << (i)) #define ull unsigned long long #define ld long double #define pb push_back #define all(x) (x).begin() , (x).end() #define BIT(x , i) ((x >> (i)) & 1) #define TASK "task" #define sz(s) (int) (s).size() using namespace std; const int mxN = 1e4 + 227; const int inf = 1e9 + 277; const int mod = 1e9 + 7; const ll infll = 1e18 + 7; const int base = 307; const int LOG = 20; const int block_sz = 550; template <typename T1, typename T2> bool minimize(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maximize(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } int n; int v[mxN]; bitset<107> dp[mxN][107]; bitset<107> dp1[107]; bitset<107> dp2[107]; vector<int> adj[mxN]; void dfs(int u, int p) { dp[u][v[u]][v[u]] = true; for(int vv : adj[u]) { if(vv == p) continue; dfs(vv, u); for(int i = 1; i <= 100; i++) { for(int j = 1; j <= 100; j++) { if(dp[vv][i][j] == true && !(i <= v[u] && v[u] <= j)) { dp[u][i][j] = true; } } } } for(int l = 100; l >= 1; l--) { for(int r = l; r <= 100; r++) { if(dp[u][l][r] == true) { dp[u][l] |= dp[u][r + 1]; } } } for(int l = 1; l <= 100; l++) { for(int r = l; r <= 100; r++) { if(!(l <= v[u] && v[u] <= r)) dp[u][l][r] = false; } } for(int l = 1; l <= 100; l++) { for(int r = l; r <= 100; r++) { //if(dp[u][l][r] == true) cout << u << ' ' << l << ' ' << r << endl; } } } void solve() { cin >> n; for(int i = 1; i <= n; i++) cin >> v[i]; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } dfs(1, -1); int res = 0; for(int i = 1; i <= 100; i++) { for(int j = i; j <= 100; j++) { res += dp[1][i][j]; } } cout << res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); //freopen("task.inp", "r", stdin); //freopen("graph.out", "w", stdout); int tc = 1; //cin >> tc; while(tc--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...