oj.uz

답안 #705364

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
705364 2023-03-04T06:58:26 Z LittleCube File Paths (BOI15_fil) C++14
0 / 100
 9 ms 4436 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int n, m, k, s, dep[6006], occ[2000006], l[6006], ans[6006];
vector<int> E[6006], cur;

void dfs(int u)
{
    if (u <= n)
    {
        cur.emplace_back(u);
        for (auto p : cur)
            occ[dep[u] - dep[p] + s]++;
        for (auto v : E[u])
        {
            dep[v] = dep[u] + l[v];
            dfs(v);
        }
        for (auto p : cur)
            occ[dep[u] - dep[p] + s]--;
        cur.pop_back();
    }
    else
    {
        ans[u] = (dep[u] == k);
        for (int i = 1; i * i <= k - dep[u]; i++)
            if((k - dep[u]) % i == 0)
            {
                int j = (k - dep[u]) / i;
                ans[u] |= (occ[i] || occ[j]);
            }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k >> s;
    s++;
    for (int i = 1; i <= n + m; i++)
    {
        int p;
        cin >> p >> l[i];
        l[i]++;
        E[p].emplace_back(i);
    }
    dfs(0);
    for (int i = n + 1; i <= n + m; i++)
        cout << (ans[i] ? "YES\n" : "NO\n");
}

Subtask #1
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 4436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -