oj.uz

Submission #675309

# Submission time Handle Problem Language Result Execution time Memory
675309 2022-12-27T03:55:30 Z vjudge1 Uzastopni (COCI15_uzastopni) C++17
160 / 160
 169 ms 18352 KB 
// Make the best become better
// No room for laziness
#include<bits/stdc++.h>

#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;
bitset<maxV> bs[maxN][maxV];
bitset<maxV> f[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)
{
    for(int v : adj[u])
    {
        dfs(v);
    }
    for(int i=1; i<=100; i++)
        f[i].reset();
    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])
                continue;
            if(l == a[u] && f[a[u] + 1][r]) bs[u][l][r] = 1;
            if(r == a[u] && f[l][a[u] - 1]) bs[u][l][r] = 1;
            if(f[l][a[u] - 1] & f[a[u] + 1][r]) bs[u][l][r] = 1;
        }
    bs[u][a[u]][a[u]] = 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 << bs[1][1][3];return;
    cout << res;
}
int32_t main()
{
    // freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 712 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 135 ms 17116 KB Output is correct
12 Correct 131 ms 17184 KB Output is correct
13 Correct 169 ms 17120 KB Output is correct
14 Correct 151 ms 18352 KB Output is correct
15 Correct 142 ms 18312 KB Output is correct
16 Correct 145 ms 18332 KB Output is correct
17 Correct 161 ms 17212 KB Output is correct
18 Correct 135 ms 17212 KB Output is correct
19 Correct 139 ms 17068 KB Output is correct
20 Correct 159 ms 17032 KB Output is correct