Submission #864944

#	Time	Username	Problem	Language	Result	Execution time	Memory
864944		hor1ey	File Paths (BOI15_fil)	C++14	0 / 100	9 ms	852 KiB

fil

#include <iostream>
#include <set>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <random>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <set>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define int long long
const int inf = 1e18;
vector<vector<int>> g;
vector<int> weigths, color;
vector<bool> answer;
vector<int> current = {0};
multiset<int> way = {0};
int n, m, k, s;
void dfs(int v, int p, int curWeight) {
    if (color[v] >= 0) {
        int val = k - curWeight - weigths[v];
        int i = 1;
        if (val == 0)
            answer[color[v]] = true;
        for (i = 1; i * i <= val; i++) {
            if (val % i == 0) {
                int curVal = val / i - s - 1;
                if (way.find(curVal) != way.end()) {
                    answer[color[v]] = true;
                }
                curVal = i - s - 1;
                if (way.find(curVal) != way.end()) {
                    answer[color[v]] = true;
                }
            }
        }
        if (i * i == val) {
            int curVal = val / i - s - 1;
            if (way.find(curVal) != way.end()) {
                answer[color[v]] = true;
            }
        }
        return;
    }
    curWeight += weigths[v];
    current.push_back(curWeight);
    for (int i = 0; i < (int)current.size() - 1; ++i) {
        way.insert(current.back() - current[i]);
    }
    for (auto to : g[v]) {
        if (to != p) {
            dfs(to, v, curWeight);
        }
    }
    for (int i = 0; i < (int)current.size() - 1; ++i) {
        way.erase(way.find(current.back() - current[i]));
    }
    current.pop_back();
}
signed main() {
    cin >> n >> m >> k >> s;
    g.resize(n + m + 2);
    weigths.resize(n + m + 2);
    color.resize(n + m + 2, -1);
    answer.resize(m + 1);
    for (int i = 0; i < n; ++i) {
        int p, l;
        cin >> p >> l;
        g[p].push_back(i + 1);
        weigths[i + 1] = l + 1;
    }
    for (int i = 0; i < m; ++i) {
        int p, l;
        cin >> p >> l;
        g[p].push_back(n + 1 + i);
        weigths[n + 1 + i] = l;
        color[n + 1 + i] = i;
    }
    dfs(0, 0, 1);
    for (int i = 0; i < m; ++i) {
        if (answer[i]) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

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