oj.uz

Submission #670731

# Submission time Handle Problem Language Result Execution time Memory
670731 2022-12-10T03:27:14 Z nonono Uzastopni (COCI15_uzastopni) C++17
160 / 160
 86 ms 32384 KB 
#include "bits/stdc++.h"
#define SZ(x) (int)(x.size())
using namespace std;

typedef bitset<100> B ;
const int mxN = 1e4 + 2, mxM = 1e2;

int n, v[mxN];
B dp[mxN][mxM];
vector<vector<int>> adj(mxN);

void dfs(int u, int pre){
    B b[mxM];

    for(int v : adj[u]){
        if(v == pre) continue ;
        dfs(v, u);

        for(int i = 0; i < mxM; i ++)
            b[i] |= dp[v][i];
    }

    for(int i = mxM - 1; i >= 0; i --){
        for(int j = i + 1; j < mxM; j ++){
            if(b[i][j - 1]) b[i] |= b[j];
        }
    }

    for(int i = 0; i <= v[u]; i ++){
        for(int j = v[u]; j < mxM; j ++)
            if(((v[u] - 1 >= 0 && b[i][v[u] - 1]) || (i == v[u])) &&
               ((v[u] + 1 < mxM && b[v[u] + 1][j]) || (j == v[u]))) dp[u][i][j] = 1;
    }
}

signed main(){
    #define file "uzastopni"
    if(fopen(file".inp", "r")){
        freopen(file".inp", "r", stdin);
        freopen(file".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    for(int i = 0; i < n; i ++){
        int x;
        cin >> x;
        v[i] = x - 1;
    }

    for(int i = 1; i < n; i ++){
        int u, v;
        cin >> u >> v;
        u = u - 1;
        v = v - 1;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(0, -1);

    int result = 0;
    for(int i = 0; i < mxM; i ++){
        result += dp[0][i].count();
    }

    cout << result ;
    return 0;
}

Compilation message

uzastopni.cpp: In function 'int main()':
uzastopni.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(file".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
uzastopni.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen(file".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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 1 ms 596 KB Output is correct
4 Correct 1 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 1 ms 832 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 708 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 66 ms 16696 KB Output is correct
12 Correct 63 ms 16716 KB Output is correct
13 Correct 60 ms 16684 KB Output is correct
14 Correct 82 ms 32332 KB Output is correct
15 Correct 86 ms 32384 KB Output is correct
16 Correct 81 ms 32352 KB Output is correct
17 Correct 59 ms 16716 KB Output is correct
18 Correct 62 ms 16716 KB Output is correct
19 Correct 75 ms 16700 KB Output is correct
20 Correct 78 ms 16696 KB Output is correct