oj.uz

Submission #675308

# Submission time Handle Problem Language Result Execution time Memory
675308 2022-12-27T03:55:18 Z tamthegod Uzastopni (COCI15_uzastopni) C++14
160 / 160
 172 ms 18508 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 3 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 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 131 ms 17168 KB Output is correct
12 Correct 128 ms 17220 KB Output is correct
13 Correct 127 ms 17232 KB Output is correct
14 Correct 135 ms 18380 KB Output is correct
15 Correct 172 ms 18508 KB Output is correct
16 Correct 131 ms 18288 KB Output is correct
17 Correct 134 ms 17144 KB Output is correct
18 Correct 135 ms 17168 KB Output is correct
19 Correct 126 ms 17068 KB Output is correct
20 Correct 153 ms 17084 KB Output is correct