oj.uz

Submission #331456

# Submission time Handle Problem Language Result Execution time Memory
331456 2020-11-28T14:31:26 Z BeanZ Uzastopni (COCI15_uzastopni) C++14
80 / 160
 125 ms 30372 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]){
                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:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   57 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
uzastopni.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   58 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
80.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 876 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Incorrect 2 ms 1004 KB Output isn't correct
4 Incorrect 2 ms 1004 KB Output isn't correct
5 Incorrect 2 ms 1004 KB Output isn't 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 3 ms 1132 KB Output is correct
10 Correct 2 ms 1004 KB Output is correct
11 Incorrect 113 ms 18028 KB Output isn't correct
12 Incorrect 112 ms 18028 KB Output isn't correct
13 Correct 121 ms 18156 KB Output is correct
14 Incorrect 123 ms 30372 KB Output isn't correct
15 Incorrect 125 ms 30188 KB Output isn't correct
16 Incorrect 122 ms 30256 KB Output isn't correct
17 Correct 121 ms 18028 KB Output is correct
18 Correct 109 ms 18028 KB Output is correct
19 Incorrect 114 ms 22508 KB Output isn't correct
20 Incorrect 120 ms 22508 KB Output isn't correct