Submission #727941

#	Time	Username	Problem	Language	Result	Execution time	Memory
727941		_martynas	File Paths (BOI15_fil)	C++11	100 / 100	87 ms	26096 KiB

fil

#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;
}

/*



*/

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