oj.uz

Submission #675272

# Submission time Handle Problem Language Result Execution time Memory
675272 2022-12-27T03:43:23 Z tamthegod Uzastopni (COCI15_uzastopni) C++14
80 / 160
 126 ms 18044 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] && f[l][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 << res;
}
int32_t main()
{
  //  freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Subtask #1
80.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Incorrect 2 ms 596 KB Output isn't correct
4 Incorrect 1 ms 596 KB Output isn't correct
5 Incorrect 1 ms 724 KB Output isn't correct
6 Correct 2 ms 744 KB Output is correct
7 Correct 2 ms 816 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Incorrect 115 ms 17168 KB Output isn't correct
12 Incorrect 110 ms 17228 KB Output isn't correct
13 Correct 109 ms 17200 KB Output is correct
14 Incorrect 104 ms 18020 KB Output isn't correct
15 Incorrect 104 ms 18012 KB Output isn't correct
16 Incorrect 102 ms 18044 KB Output isn't correct
17 Correct 119 ms 17172 KB Output is correct
18 Correct 126 ms 17164 KB Output is correct
19 Incorrect 109 ms 17012 KB Output isn't correct
20 Incorrect 106 ms 17100 KB Output isn't correct