Submission #727941

#TimeUsernameProblemLanguageResultExecution timeMemory
727941_martynasFile Paths (BOI15_fil)C++11
100 / 100
87 ms26096 KiB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

const int MXN = 6005;
const int MXR = 1e6+5;

int n, m, k, s;
vi adj[MXN];
ll len[MXN], path[MXN];
bool path_present[MXR];
bool ans[MXN];
vi cycles[MXN];
int cycle_cnt[MXR];

vi up;
void init_cycles(int u, int p) {
    if(u > n) return;
    up.PB(u);
    for(int v : up) {
        cycles[v].PB(path[u]-path[v]+s);
    }
    for(int v : adj[u]) if(v != p) {
        init_cycles(v, u);
    }
    up.pop_back();
}

void upd(int sum, int change) {
    if(sum >= MXR) return;
    cycle_cnt[sum] += change;
}

vi get_divs(int sum) {
    vi divs;
    for(int i = 1; i*i <= sum; i++) {
        if(sum % i) continue;
        divs.PB(i);
        if(i != sum/i) divs.PB(sum/i);
    }
    return divs;
}

void dfs(int u, int p) {
    up.PB(u);
    if(u > n) {
        ans[u] = path[u] == k;
        for(int v : up) {
            if(k-(path[u]-path[v]+len[v]+s) >= 0
               && path_present[k-(path[u]-path[v]+len[v]+s)])
                ans[u] = true;
        }
        if(path[u] < k) {
            vi divs = get_divs(k-path[u]);
            for(int x : divs) {
                if(cycle_cnt[x]) ans[u] = true;
            }
        }
        up.pop_back();
        return;
    }
    for(int sum : cycles[u]) upd(sum, 1);
    for(int v : adj[u]) if(v != p) {
        dfs(v, u);
    }
    up.pop_back();
    for(int sum : cycles[u]) upd(sum, -1);
}

int main() {
    cin >> n >> m >> k >> s; s++;
    path_present[0] = true;
    for(int i = 1; i <= n; i++) {
        int p; cin >> p >> len[i]; len[i]++;
        adj[p].PB(i);
        path[i] += path[p]+len[i];
        path_present[path[i]] = true;
    }
    for(int i = n+1; i <= n+m; i++) {
        int p; cin >> p >> len[i]; len[i]++;
        adj[p].PB(i);
        path[i] += path[p]+len[i];
    }
    init_cycles(0, -1);
    dfs(0, -1);
    for(int i = n+1; i <= n+m; i++) cout << (ans[i] ? "YES\n" : "NO\n");
    return 0;
}

/*



*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...