oj.uz

Submission #1051413

# Submission time Handle Problem Language Result Execution time Memory
1051413 2024-08-10T06:20:10 Z 12345678 File Paths (BOI15_fil) C++17
33 / 100
 379 ms 32576 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=6e3+5, kx=1e6+5;

int n, m, k, sz, pa[nx], dist[nx], w, res[nx], cnt[kx], vs[kx];
vector<pair<int, int>> d[nx];
vector<int> fact[kx];

void dfs(int u)
{
    for (auto [v, w]:d[u]) dist[v]=dist[u]+w, dfs(v);
}

void dfs3(int u, int vl, int rt)
{
    if (dist[u]-dist[rt]+sz+1<=k) cnt[dist[u]-dist[rt]+sz+1]+=vl;
    for (auto [v, w]:d[u]) if (v<=n) dfs3(v, vl, rt);
}

void dfs2(int u)
{
    if (u<=n) dfs3(u, 1, u);
    if (u>n) for (auto x:fact[k-dist[u]]) if (cnt[x]>0) res[u]=1;
    for (auto [v, w]:d[u]) dfs2(v);
    if (u<=n) dfs3(u, -1, u);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>k>>sz;
    for (int i=1; i<=n; i++) cin>>pa[i]>>w, d[pa[i]].push_back({i, w+1});
    for (int i=n+1; i<=n+m; i++) cin>>pa[i]>>w, d[pa[i]].push_back({i, w+1});
    dfs(0);
    for (int i=n+1; i<=n+m; i++) vs[k-dist[i]]=1; 
    for (int i=2; i<=k; i++) for (int j=i; j<=k; j+=i) if (vs[j]) fact[j].push_back(i);
    dfs2(0);
    for (int i=n+1; i<=n+m; i++)
    {
        if (dist[i]==k) res[i]=1;
        set<int> s;
        s.insert(0);
        int tmp=i;
        while (tmp!=0) s.insert(dist[i]-dist[pa[tmp]]), tmp=pa[tmp];
        for (int j=0; j<=n; j++) if (s.find(k-dist[j]-sz-1)!=s.end()) res[i]=1;
        if (res[i]) cout<<"YES\n";
        else cout<<"NO\n"; 
    }
}

Subtask #1
0 / 33.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 32092 KB Output is correct
2 Correct 67 ms 32092 KB Output is correct
3 Correct 69 ms 32084 KB Output is correct
4 Correct 64 ms 32228 KB Output is correct
5 Correct 350 ms 32576 KB Output is correct
6 Correct 355 ms 32336 KB Output is correct
7 Correct 224 ms 32340 KB Output is correct
8 Correct 240 ms 32172 KB Output is correct
9 Correct 61 ms 32236 KB Output is correct
10 Correct 46 ms 30296 KB Output is correct
11 Correct 70 ms 25436 KB Output is correct
12 Correct 379 ms 26964 KB Output is correct

Subtask #3
0 / 34.0

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