oj.uz

Submission #675481

# Submission time Handle Problem Language Result Execution time Memory
675481 2022-12-27T10:32:48 Z messiuuuuu Uzastopni (COCI15_uzastopni) C++17
136 / 160
 197 ms 65536 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 = 1e5 + 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];

void DFS(int u, int par)
{
    vector<int> pl[105], pr[105];
    for (int v : Adj[u])
    {
        if (v == par)
            continue;
        DFS(v, u);
        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);
                }
    }
    for (int i = 1; i <= 100; i++)
        t[i].reset();
    vector<int> lf, rg;
    t[c[u]] = 1;
    lf.pb(c[u]);
    rg.pb(c[u]);
    for (int i = 100; i >= c[u] + 1; i--)
    {
        for (int j : pl[i])
        {
            t[i][j] = 1;
            t[i] |= t[j + 1];
        }
        if (i == c[u] + 1)
        {
            for (int j = 1; j <= 100; j++)
                if (t[i][j])
                    rg.pb(j);
        }
    }
    for (int i = 1; i <= c[u] - 1; i++)
    {
        for (int j : pr[i])
        {
            t[i][j] = 1;
            t[i] |= t[j - 1];
        }
        if (i == c[u] - 1)
        {
            for (int j = 1; j <= 100; j++)
                if (t[i][j])
                    lf.pb(j);
        }
    }
    for (int x : lf)
    {
        for (int y : rg)
        {
            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:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
136.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 4 ms 3156 KB Output is correct
7 Correct 4 ms 3156 KB Output is correct
8 Correct 4 ms 3156 KB Output is correct
9 Correct 4 ms 2772 KB Output is correct
10 Correct 4 ms 2872 KB Output is correct
11 Correct 180 ms 19532 KB Output is correct
12 Correct 173 ms 19508 KB Output is correct
13 Correct 173 ms 19544 KB Output is correct
14 Runtime error 192 ms 65536 KB Execution killed with signal 9
15 Runtime error 197 ms 65536 KB Execution killed with signal 9
16 Runtime error 188 ms 65536 KB Execution killed with signal 9
17 Correct 172 ms 19532 KB Output is correct
18 Correct 183 ms 19468 KB Output is correct
19 Correct 175 ms 19784 KB Output is correct
20 Correct 173 ms 19776 KB Output is correct