Submission #1143515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143515		dpsaveslives	File Paths (BOI15_fil)	C++20	100 / 100	611 ms	31688 KiB

fil

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

const int MAXN = 6005;
const int MAXK = 1e6+5;
int N,M,K,w,sz;
int par[MAXN],dist[MAXN],ans[MAXN],cnt[MAXK],vis[MAXK];
vector<pair<int,int>> adj[MAXN];
vector<int> fact[MAXK];
void dfs(int u){
    for(auto x : adj[u]){
        dist[x.f] = dist[u]+x.s;
        dfs(x.f);
    }
}

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 x : adj[u]){
        if(x.f <= N){
            dfs3(x.f,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){
                ans[u] = 1;
            }
        }
    }
    for(auto x : adj[u]){
        dfs2(x.f);
    }
    if(u <= N){
        dfs3(u,-1,u);
    }
}


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> M >> K >> sz;
    for(int i = 1;i<=N;++i){
        cin >> par[i] >> w;
        adj[par[i]].push_back({i,w+1});
    }
    for(int i = N+1;i<=N+M;++i){
        cin >> par[i] >> w;
        adj[par[i]].push_back({i,w+1});
    }
    dfs(0);
    for(int i = N+1;i<=N+M;++i){
        vis[K-dist[i]] = 1;
    }
    for(int i = 2;i<=K;++i){
        for(int j = i;j<=K;j += i){
            if(vis[j]){
                fact[j].push_back(i);
            }
        }
    }
    dfs2(0);
    for(int i = N+1;i<=N+M;++i){
        if(dist[i] == K) ans[i] = 1;
        set<int> s;
        int tmp = i;
        while(tmp != 0){
            s.insert(dist[i]-dist[par[tmp]]);
            tmp = par[tmp];
        }
        for(int j = 0;j<=N;++j){
            if(s.find(K-dist[j]-sz-1) != s.end()){
                ans[i] = 1;
            }
        }
        if(ans[i]){
            cout << "YES\n";
        }
        else{
            cout << "NO\n";
        }
    }
    return 0;
}

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