oj.uz

답안 #677895

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
677895 2023-01-04T14:47:23 Z vjudge1 Uzastopni (COCI15_uzastopni) C++17
160 / 160
 175 ms 18528 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 704 KB Output is correct
5 Correct 2 ms 704 KB Output is correct
6 Correct 2 ms 700 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 700 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 163 ms 17404 KB Output is correct
12 Correct 161 ms 17472 KB Output is correct
13 Correct 170 ms 17344 KB Output is correct
14 Correct 171 ms 18456 KB Output is correct
15 Correct 170 ms 18528 KB Output is correct
16 Correct 165 ms 18492 KB Output is correct
17 Correct 175 ms 17484 KB Output is correct
18 Correct 163 ms 17476 KB Output is correct
19 Correct 158 ms 17740 KB Output is correct
20 Correct 158 ms 17612 KB Output is correct