oj.uz

Submission #218116

# Submission time Handle Problem Language Result Execution time Memory
218116 2020-04-01T09:06:11 Z dolphingarlic File Paths (BOI15_fil) C++14
0 / 100
 17 ms 7552 KB 
#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<int> graph[6001];
int to_root[6001], par[6001], can[1000001], cyc[1000001];
bool reachable[6001];

void add_cycles(int node, int root, int val) {
    if (node <= n) cyc[to_root[node] - to_root[root] + s] += val;
    for (int i : graph[node]) add_cycles(i, root, val);
}

void dfs(int node = 0) {
    if (node > n) {
        int add_dist = k - to_root[node];
        if (add_dist == 0) reachable[node] = true;
        for (int i = 1; i * i <= add_dist; i++) if (add_dist % i == 0 && (cyc[i] || cyc[add_dist / i])) reachable[node] = true;
        for (int i = par[node]; ~i; i = par[i]) if (add_dist - s + to_root[i] >= 0 && can[add_dist - s + to_root[i]]) reachable[node] = true;
    } else {
        for (int i = node; ~i; i = par[i]) cyc[to_root[node] - to_root[i] + s]++;
        add_cycles(node, node, 1);
        for (int i : graph[node]) dfs(i);
        for (int i = node; ~i; i = par[i]) cyc[to_root[node] - to_root[i] + s]--;
        add_cycles(node, node, -1);
    }
}

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

        if (i <= n && to_root[i] <= k) can[to_root[i]]++;
    }
    dfs();

    FOR(i, n + 1, n + m + 1) cout << (reachable[i] ? "YES\n" : "NO\n");
    return 0;
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 6 ms 1280 KB Output is correct
4 Correct 10 ms 1280 KB Output is correct
5 Incorrect 11 ms 5120 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

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

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 6 ms 1280 KB Output is correct
4 Correct 10 ms 1280 KB Output is correct
5 Incorrect 11 ms 5120 KB Output isn't correct
6 Halted 0 ms 0 KB -