oj.uz

Submission #675485

# Submission time Handle Problem Language Result Execution time Memory
675485 2022-12-27T10:40:53 Z messiuuuuu Uzastopni (COCI15_uzastopni) C++17
160 / 160
 168 ms 18456 KB 
///
#include<bits/stdc++.h>
#define task "C"
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 1e4 + 5;
const ll INF = 1e18 + 5;

int n;
int c[MAXN];
vector<int> Adj[MAXN];

void Input()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        Adj[u].pb(v);
        Adj[v].pb(u);
    }
}

bitset<105> dp[MAXN][105], t[105];
vector<int> pl[105], pr[105];

void DFS(int u, int par)
{
    for (int v : Adj[u])
    {
        if (v == par)
            continue;
        DFS(v, u);
    }
    for (int i = 1; i <= 100; i++)
    {
        t[i].reset();
        pl[i].clear();
        pr[i].clear();
    }
    for (int v : Adj[u])
    {
        if (v == par)
            continue;
        for (int l = 1; l <= 100; l++)
            for (int r = l; r <= 100; r++)
                if (dp[v][l][r])
                {
                    pl[l].pb(r);
                    pr[r].pb(l);
                }
    }
    t[c[u] - 1][c[u]] = t[c[u] + 1][c[u]] = 1;
    for (int i = 100; i >= c[u] + 1; i--)
    {
        for (int j : pl[i])
        {
            t[i][j] = 1;
            t[i] |= t[j + 1];
        }
    }
    for (int i = 1; i <= c[u] - 1; i++)
    {
        for (int j : pr[i])
        {
            t[i][j] = 1;
            t[i] |= t[j - 1];
        }
    }
    for (int x = 1; x <= 100; x++)
    {
        if (t[c[u] - 1][x] == 0)
            continue;
        for (int y = x; y <= 100; y++)
        {
            if (t[c[u] + 1][y] == 0)
                continue;
            dp[u][x][y] = 1;
        }
    }
}

void Solve()
{
    DFS(1, 0);
    int res = 0;
    for (int i = 1; i <= 100; i++)
    {
        for (int j = i; j <= 100; j++)
        {
            //if (dp[1][i][j])
             //   cout << i << ' ' << j << '\n';
            res += dp[1][i][j];
        }
    }
    cout << res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(task".INP","r"))
    {
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    Input();
    Solve();
}

Compilation message

uzastopni.cpp: In function 'int main()':
uzastopni.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
160.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 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 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 3 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 159 ms 17296 KB Output is correct
12 Correct 160 ms 17228 KB Output is correct
13 Correct 162 ms 17324 KB Output is correct
14 Correct 168 ms 18360 KB Output is correct
15 Correct 161 ms 18412 KB Output is correct
16 Correct 164 ms 18456 KB Output is correct
17 Correct 157 ms 17276 KB Output is correct
18 Correct 158 ms 17320 KB Output is correct
19 Correct 157 ms 17524 KB Output is correct
20 Correct 159 ms 17736 KB Output is correct