oj.uz

Submission #331458

# Submission time Handle Problem Language Result Execution time Memory
331458 2020-11-28T14:33:25 Z BeanZ Uzastopni (COCI15_uzastopni) C++14
160 / 160
 95 ms 29992 KB 
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1e4 + 5;
const int mod = 1e9 + 7;
const int lim = 100;
bitset<101> bit[N][105];
vector<ll> node[N], d[101];
vector<pair<ll, ll>> q[N];
ll a[N];

/*
  Sol: Goi q[u] la tat ca cac cap (l, r) sao cho subtree cua u co the lam dc 1 doan (l, r)
  Goi bit[u][l] la mot mang bool neu bit thu r cua mang nay bat tuc la doan (l, r) trong subtree u co the lam dc
  bit[u][l] dc tinh bang cach xet toan bo cac node con cua u
  Ta se tinh dc q[u] cua tung node con cua u
  Khi do ta xem tat ca cac cap (lf, rt) ma lf == l
  {
      bit[u][l] |= bit[u][r + 1] (de tranh bi lay 2 joke chung nen se lay bit tu r + 1 tro di)
      bit[u][l].set(r) (tu cai dat cho no rang (l, r) dc)
  }
  Sau do voi moi doan (l, r) dc tao thanh ta kiem tra xem l <= a[u] && r >= a[u] ko roi them no vao q[u]
  de tinh cho cha cua u.
*/

void dfs(ll u){
    for (auto j : node[u]) dfs(j);
    for (int i = 1; i <= lim; i++) d[i].clear();
    for (auto j : node[u]){
        for (auto t : q[j]){
            d[t.first].push_back(t.second);
        }
    }
    for (int i = lim; i >= 1; i--){
        if (a[u] == i){
            bit[u][i].set(i);
            bit[u][i] |= bit[u][i + 1];
        } else {
            for (auto r : d[i]){
                if (r < a[u] || i > a[u]){
                    bit[u][i].set(r);
                    bit[u][i] |= bit[u][r + 1];
                }
            }
        }
        for (int r = lim; r >= i; r--){
            if (bit[u][i][r] && a[u] >= i && a[u] <= r){
                q[u].push_back({i, r});
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("A.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++){
        ll u, v;
        cin >> u >> v;
        node[u].push_back(v);
    }
    dfs(1);
    cout << q[1].size();
}
/*
*/

Compilation message

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

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 876 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 2 ms 1004 KB Output is correct
5 Correct 2 ms 1004 KB Output is correct
6 Correct 2 ms 1004 KB Output is correct
7 Correct 2 ms 1004 KB Output is correct
8 Correct 2 ms 1004 KB Output is correct
9 Correct 2 ms 1004 KB Output is correct
10 Correct 2 ms 1004 KB Output is correct
11 Correct 83 ms 17900 KB Output is correct
12 Correct 82 ms 17900 KB Output is correct
13 Correct 86 ms 18028 KB Output is correct
14 Correct 95 ms 29992 KB Output is correct
15 Correct 94 ms 29932 KB Output is correct
16 Correct 95 ms 29932 KB Output is correct
17 Correct 83 ms 17900 KB Output is correct
18 Correct 85 ms 18028 KB Output is correct
19 Correct 87 ms 22380 KB Output is correct
20 Correct 85 ms 22380 KB Output is correct