oj.uz

Submission #675266

# Submission time Handle Problem Language Result Execution time Memory
675266 2022-12-27T03:41:59 Z tamthegod Uzastopni (COCI15_uzastopni) C++14
80 / 160
 122 ms 17724 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;
}
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 1 ms 596 KB Output isn't correct
4 Incorrect 2 ms 596 KB Output isn't correct
5 Incorrect 1 ms 724 KB Output isn't 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 3 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Incorrect 122 ms 17208 KB Output isn't correct
12 Incorrect 115 ms 17236 KB Output isn't correct
13 Correct 113 ms 17188 KB Output is correct
14 Incorrect 108 ms 17724 KB Output isn't correct
15 Incorrect 112 ms 17720 KB Output isn't correct
16 Incorrect 107 ms 17716 KB Output isn't correct
17 Correct 117 ms 17172 KB Output is correct
18 Correct 112 ms 17160 KB Output is correct
19 Incorrect 117 ms 17100 KB Output isn't correct
20 Incorrect 106 ms 17012 KB Output isn't correct