Submission #521304

#	Time	Username	Problem	Language	Result	Execution time	Memory
521304		radal	File Paths (BOI15_fil)	C++14	100 / 100	273 ms	5756 KiB

fil

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
//#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
const long long int N = 6e3+20,mod = 998244353,inf = 1e9+10,maxm = 2e6+10,sq = 1001;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}

inline int poww(int a,int k){
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    }
    return z;
}
int h[N],n,m,k,s,par[N],L[N];;
int cnt[maxm];
bool b[maxm];
vector<pll> adj[N];
bool ok[N];
void dfs2(int u,int v,int t){
    if (u <= n) cnt[h[u]-h[v]+s] += t;
    for (pll w : adj[u]) dfs2(w.X,v,t);
}
void dfs(int v){
    if (v <= n){
        b[h[v]] = 1;
        int w = v;
        while (w > -1){
            cnt[h[v]-h[w]+s]++;
            w = par[w];
        }
        dfs2(v,v,1);
    }
    else{
        if(k == h[v]) ok[v] = 1;
        rep(i,1,sq+1){
            if (ok[v]) break;
            if ((k-h[v])%i) continue;
            if (cnt[(k-h[v])/i] || cnt[i]){
                ok[v] = 1;
                break;
            }
        }
        return;
    }
    for(pll u : adj[v]){
        dfs(u.X);
    }
    dfs2(v,v,-1);
    int w = v;
    while (w > -1){
        cnt[h[v]-h[w]+s]--;
        w = par[w];
    }
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    cin >> n >> m >> k >> s;
    s++;
    rep(i,1,n+1){
        int p,l;
        cin >> p >> l;
        par[i] = p;
        h[i] = h[p]+l+1;
        adj[p].pb({i,l+1});
    }
    rep(i,1,m+1){
        int p,l;
        cin >> p >> l;
        par[i+n] = p;
        h[i+n] = h[p]+l+1;
        L[i] = l;
        adj[p].pb({i+n,l+1});
    }
    par[0] = -1;
    dfs(0);
    rep(i,1,m+1){
        if (k  == h[i+n]){
            cout << "YES" << endl;
            continue;
        }
        int v = par[i+n];
        while (v >= 0){
            int t = s+h[i+n]-h[v];
            if (k >= t && b[k-t]){
                ok[i+n] = 1;
                break;
            }
            v = par[v];
        }
        if (ok[i+n]){
            cout << "YES" << endl;
            continue;
        }
        cout << "NO" << endl;
    }
}

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