oj.uz

Submission #675257

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

#define int long long
#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;
bool can[maxN];
bitset<maxV> bs[maxN][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)
{
    bs[u][a[u]][a[u]] = 1;
    for(int v : adj[u])
    {
        dfs(v);
    }
    bitset<maxV> f[maxV];
    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()
{
    for(int i=1; i<=n; i++)
        if(!deg[i])
            root = i;
    dfs(root);
 //   cout << bs[1][3][4];return;
    int res = 0;
    for(int l=1; l<=100; l++)
        for(int r=l; r<=100; r++)
            res += bs[root][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 2 ms 596 KB Output is correct
3 Incorrect 2 ms 596 KB Output isn't correct
4 Incorrect 2 ms 596 KB Output isn't correct
5 Incorrect 2 ms 724 KB Output isn't correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 828 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 704 KB Output is correct
11 Incorrect 131 ms 17380 KB Output isn't correct
12 Incorrect 129 ms 17420 KB Output isn't correct
13 Correct 126 ms 17404 KB Output is correct
14 Runtime error 130 ms 34056 KB Memory limit exceeded
15 Runtime error 129 ms 34048 KB Memory limit exceeded
16 Runtime error 130 ms 34060 KB Memory limit exceeded
17 Correct 139 ms 17428 KB Output is correct
18 Correct 130 ms 17412 KB Output is correct
19 Incorrect 113 ms 17368 KB Output isn't correct
20 Incorrect 120 ms 17348 KB Output isn't correct