Submission #985830

#	Time	Username	Problem	Language	Result	Execution time	Memory
985830		hengliao	File Paths (BOI15_fil)	C++17	33 / 100	122 ms	74648 KiB

fil

#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef int ll;

const ll mxN=3005;

vll adj[mxN]; 
ll dis[mxN]; 
ll lef[mxN];
ll rig[mxN];
ll p[2*mxN];
ll l[2*mxN];
vll mul[mxN]; //144
vll add[mxN]; // 144
bool ans[2*mxN]; // 16
ll cnt[1000005];  //16
ll cnt2[1000005]; //16
ll timer=0;

ll n, m, k, s;

void builddis(ll cur, ll d){
    if(cur>n) return;
    dis[cur]=d;
    lef[cur]=timer;
    timer++;
    for(auto &chd:adj[cur]){
        builddis(chd, d+l[chd]+1);
    }
    rig[cur]=timer;
}

bool under(ll a, ll b){
    return lef[a]>=lef[b] && rig[a]<=rig[b];
}

void addedge(ll a, ll b){
    if(under(a, b)){
        mul[b].pb(dis[a]-dis[b]+s+1);
    }
    else{
        ll newdis=dis[a]+s+1;
        ll dif=newdis-dis[b];
        if(dif>0){
            add[b].pb(dif);
        }
    }
}

void dfs(ll cur, ll d){
    if(cur>n){
        ll need=k-d;
        if(need==0){
            ans[cur]=1;
            return;
        }
        if(cnt[need]){
            ans[cur]=1;
            return;
        }
        for(ll i=1;i*i<=need;i++){
            if(need%i==0){
                if(cnt2[i] || cnt2[need/i]){
                    ans[cur]=1;
                    return;
                }
            }
        }
        ans[cur]=0;
    }
    for(auto &it:add[cur]){
        if(it<1000005) cnt[it]++;
    }
    for(auto &it:mul[cur]){
        if(it<1000005) cnt2[it]++;
    }
    for(auto &chd:adj[cur]){
        dfs(chd, d+l[chd]+1);
    }
    for(auto &it:add[cur]){
        if(it<1000005) cnt[it]--;
    }
    for(auto &it:mul[cur]){
        if(it<1000005) cnt2[it]--;
    }
}

void solve(){
	memset(dis, -1, sizeof(dis));
    cin>>n>>m>>k>>s;
    l[0]=0;
    for(ll i=1;i<=n;i++){
        cin>>p[i]>>l[i];
        adj[p[i]].pb(i);
    }
    for(ll i=n+1;i<=n+m;i++){
        cin>>p[i]>>l[i];
        adj[p[i]].pb(i);
    }
    builddis(0, 0);

    for(ll i=0;i<=n;i++){
        for(ll j=0;j<=n;j++){
            addedge(i, j);
        }
    }

    dfs(0, 0);

    for(ll i=n+1;i<=n+m;i++){
        if(ans[i]){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
    }    
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solve();
	return 0;
}

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