Submission #675262

#TimeUsernameProblemLanguageResultExecution timeMemory
675262tamthegodUzastopni (COCI15_uzastopni)C++14
80 / 160
133 ms33960 KiB
// Make the best become better // No room for laziness #include<bits/stdc++.h> #define int long long #define pb push_back #define fi first #define se second using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 1e4 + 5; const int maxV = 105; const int mod = 1e9 + 7; const ll oo = 1e18; int n; int a[maxN]; vector<int> adj[maxN]; int deg[maxN]; int root; bool can[maxN]; bitset<maxV> bs[maxN][maxV]; void ReadInput() { 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].pb(v); deg[v]++; } } void dfs(int u) { bs[u][a[u]][a[u]] = 1; for(int v : adj[u]) { dfs(v); } bitset<maxV> f[maxV]; f[a[u]][a[u]] = 1; for(int v : adj[u]) { for(int l=1; l<=100; l++) f[l] |= bs[v][l]; } for(int l=1; l<=100; l++) for(int r=l; r<=100; r++) if(f[l][r]) f[l] |= f[r + 1]; for(int l=1; l<=100; l++) for(int r=l; r<=100; r++) if(l <= a[u] && r >= a[u] && f[l][r]) bs[u][l][r] = 1; } void Solve() { dfs(1); int res = 0; for(int l=1; l<=100; l++) for(int r=l; r<=100; r++) res += bs[1][l][r]; cout << res; } int32_t main() { // freopen("x.inp", "r", stdin); ios_base::sync_with_stdio(false); cin.tie(nullptr); ReadInput(); Solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...