oj.uz

Submission #864944

# Submission time Handle Problem Language Result Execution time Memory
864944 2023-10-23T18:55:33 Z hor1ey File Paths (BOI15_fil) C++14
0 / 100
 9 ms 852 KB 
#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.0

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

Subtask #2
0 / 33.0

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

Subtask #3
0 / 34.0

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