oj.uz

답안 #675466

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
675466 2022-12-27T10:09:33 Z messiuuuuu Uzastopni (COCI15_uzastopni) C++17
136 / 160
 182 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 = 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];

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);
                }
    }
    bitset<105> t[105];
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 800 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 4 ms 1108 KB Output is correct
8 Correct 2 ms 1108 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 174 ms 17484 KB Output is correct
12 Correct 168 ms 17460 KB Output is correct
13 Correct 171 ms 17572 KB Output is correct
14 Runtime error 39 ms 65536 KB Execution killed with signal 9
15 Runtime error 40 ms 65536 KB Execution killed with signal 9
16 Runtime error 41 ms 65536 KB Execution killed with signal 9
17 Correct 179 ms 17488 KB Output is correct
18 Correct 171 ms 17452 KB Output is correct
19 Correct 178 ms 17740 KB Output is correct
20 Correct 182 ms 17672 KB Output is correct