oj.uz

Submission #675287

# Submission time Handle Problem Language Result Execution time Memory
675287 2022-12-27T03:49:34 Z tamthegod Uzastopni (COCI15_uzastopni) C++14
80 / 160
 174 ms 18220 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;
        }
    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 Incorrect 2 ms 596 KB Output isn't correct
3 Incorrect 2 ms 596 KB Output isn't correct
4 Incorrect 1 ms 596 KB Output isn't correct
5 Incorrect 2 ms 724 KB Output isn't correct
6 Correct 3 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 3 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 162 ms 17220 KB Output is correct
12 Incorrect 155 ms 17120 KB Output isn't correct
13 Incorrect 139 ms 17180 KB Output isn't correct
14 Correct 147 ms 18208 KB Output is correct
15 Correct 145 ms 18140 KB Output is correct
16 Correct 153 ms 18220 KB Output is correct
17 Incorrect 162 ms 17156 KB Output isn't correct
18 Incorrect 142 ms 17184 KB Output isn't correct
19 Incorrect 138 ms 17108 KB Output isn't correct
20 Incorrect 174 ms 17008 KB Output isn't correct