Submission #668664

#	Time	Username	Problem	Language	Result	Execution time	Memory
668664		ParsaS	File Paths (BOI15_fil)	C++17	100 / 100	229 ms	30404 KiB

fil

// 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], mark[M];
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;
    else
        mark[k - 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) {
            if (mark[j])
                _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 (stderr)

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

• Subtask 1: 33 / 33
• Subtask 2: 33 / 33
• Subtask 3: 34 / 34