Submission #218079

#	Time	Username	Problem	Language	Result	Execution time	Memory
218079		dolphingarlic	File Paths (BOI15_fil)	C++14	0 / 100	14 ms	6016 KiB

fil

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, m, k, s;
vector<pair<int, int>> graph[6001];
bitset<6001> subtree[6001];
int to_root[6001];
bool can[1000001];

void get_subtree(int node = 0) {
    for (pair<int, int> i : graph[node]) {
        to_root[i.first] = to_root[node] + i.second;
        get_subtree(i.first);
        subtree[node] |= subtree[i.first];
    }
}

bool reachable(int leaf, int node = 0) {
    if (to_root[leaf] > k) {
        vector<int> ancestors;
        FOR(i, 0, n + 1) if (subtree[i][leaf]) ancestors.push_back(i);

        int lptr = 0;
        FOR(rptr, 1, ancestors.size()) {
            while (to_root[lptr] + s + to_root[leaf] - to_root[rptr] < k) lptr++;
            if (to_root[lptr] + s + to_root[leaf] - to_root[rptr] == k) return true;
        }
        return false;
    } else return can[k - to_root[leaf]];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k >> s;
    FOR(i, 1, n + m + 1) {
        subtree[i][i] = 1;
        int p, l;
        cin >> p >> l;
        graph[p].push_back({i, l});
    }
    get_subtree();

    can[0] = true;
    FOR(i, 0, n + 1) FOR(j, i, n + 1) if (subtree[i][j]) {
        int period = s + to_root[j] - to_root[i];
        if (can[period]) continue;
        for (int x = period; x <= k; x += period) can[x] = true;
    }

    FOR(i, n, n + m) {
        if (reachable(i)) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

Compilation message (stderr)

fil.cpp: In function 'bool reachable(int, int)':
fil.cpp:2:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
fil.cpp:26:13:
         FOR(rptr, 1, ancestors.size()) {
             ~~~~~~~~~~~~~~~~~~~~~~~~~   
fil.cpp:26:9: note: in expansion of macro 'FOR'
         FOR(rptr, 1, ancestors.size()) {
         ^~~

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