oj.uz

Submission #668602

# Submission time Handle Problem Language Result Execution time Memory
668602 2022-12-04T08:42:50 Z radal File Paths (BOI15_fil) C++17
33 / 100
 188 ms 29392 KB 
// In the name of God
#pragma GCC optimize("O2", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 6000 + 5, M = 1e6 + 10;
int n, m, k, s;
int par[N], l[N], h[N];
vector<int> adj[N], vec, _div[M], V[N];
bool check[M], ans[N];
int vis[M];
 
void dfs(int v) {
    for (auto u : adj[v]) {
        h[u] = h[v] + l[u];
        dfs(u);
    }
    if (v <= n)
        check[h[v]] = true;
}
void dfs3(int v, int p, int t) {
    if (v <= n)
        vis[h[v] - h[p]] += t;
    for (auto u : adj[v])
        dfs3(u, p, t);
}
inline void upd(int v, int t) {
    dfs3(v, v, t);
}
void dfs2(int v) {
    vec.pb(v);
    if (v <= n) {
        upd(v, 1);
        for (auto u : adj[v]) {
            dfs2(u);
        }
        upd(v, -1);
        vec.pop_back();
        return;
    }
    ans[v] |= h[v] == k;
    for (int i = 0; !ans[v] && i < vec.size() - 1; i++) {
        ans[v] |= k >= h[v] - h[vec[i]] + s && check[k - h[v] + h[vec[i]] - s];
        ans[v] |= k >= h[v] + s && check[k - h[v] - s];
    }
    int L = k - h[v];
    ans[v] |= L >= s && vis[L - s];
    /*for (auto d : _div[L]) {
        ans[v] |= vis[d - s];
        if (ans[v])
            break;
    }*/
    vec.pop_back();
}
 
void solve() {
    cin >> n >> m >> k >> s;
    s++;
    for (int i = 1; i <= n; i++) {
        cin >> par[i] >> l[i];
        l[i]++;
        adj[par[i]].pb(i);
    }
    for (int i = 1; i <= m; i++) {
        cin >> par[i + n] >> l[i + n];
        l[i + n]++;
        adj[par[i + n]].pb(i + n);
    }
    dfs(0);
    /*for (int i = s; i <= k; i++) {
        for (int j = i; j <= k; j += i) {
            _div[j].pb(i);
        }
    }*/
    dfs2(0);
    for (int i = n + 1; i <= n + m; i++)
        cout << (ans[i] ? "YES" : "NO") << '\n';
}
 
int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
 
    return 0;
}

Compilation message

fil.cpp: In function 'void dfs2(int)':
fil.cpp:46:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; !ans[v] && i < vec.size() - 1; i++) {
      |                                ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 24020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28984 KB Output is correct
2 Correct 17 ms 28980 KB Output is correct
3 Correct 18 ms 29100 KB Output is correct
4 Correct 18 ms 28972 KB Output is correct
5 Correct 166 ms 29348 KB Output is correct
6 Correct 173 ms 29392 KB Output is correct
7 Correct 95 ms 29224 KB Output is correct
8 Correct 103 ms 29224 KB Output is correct
9 Correct 18 ms 29012 KB Output is correct
10 Correct 18 ms 29012 KB Output is correct
11 Correct 19 ms 24336 KB Output is correct
12 Correct 188 ms 26284 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 24020 KB Output isn't correct
2 Halted 0 ms 0 KB -