Submission #1173120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173120		ThommyDB	File Paths (BOI15_fil)	C++20	33 / 100	1095 ms	584 KiB

fil

#include<bits/stdc++.h>

using namespace std;

int n, m, k, s;
vector<int> p, l, in, out, sz;
vector<vector<int>> chi;
int T = 0,szz = 0;

void dfs(int x){
	in[x] = T;
    T++;
	szz += l[x];
    sz[x] = szz;
    for(auto u : chi[x]){
        dfs(u);
    }
	out[x] = T;
    T++;
	szz -= l[x];
}

bool below(int a, int b){
    //cout << "for " << a << " and " << b << ":" << in[a] << " vs " << in[b] << " und " << out[a] << " vs " << out[b] << "\n";
	if(in[a] > in[b]) return false;
	if(out[a] < out[b]) return false;
	return true;
}

bool check(int a,int b){
	if(sz[a] + b == k) return true;

    int j = a;
    for(int i = 0; i <= n; i++){
        if(sz[a]+sz[i]-sz[j]+s+b == k){
            //cout << i << " " << j << "\n";
            return true;
        }
        if(!below(j,i)) continue;
		if((k - b-sz[a]) % (s+sz[i]-sz[j]) == 0){
            //cout << i << " " << j << "\n";
            return true;
        }
    }
    while(j!=0){
        j=p[j];
        for(int i = 0; i <= n; i++){
            if(sz[a]+sz[i]-sz[j]+s+b == k){
                //cout << i << " " << j << "\n";
                return true;
            }
            if(!below(j,i)) continue;
            if((k - b-sz[a]) % (s+sz[i]-sz[j]) == 0){
                //cout << i << " " << j << "\n";
                return true;
            }
        }
    }
	
    /*for(int i = 0; i <= n; i++){
        for(int j = 0; j <=n; j++){
            if(!below(j,a)) continue;
		    if(sz[a]+sz[i]-sz[j]+s+b == k){
                //cout << i << " " << j << "\n";
                return true;
            }
		    if(!below(j,i)) continue;
		    if((k - b-sz[a]) % (s+sz[i]-sz[j]) == 0){
                //cout << i << " " << j << "\n";
                return true;
            }
        }
    }*/
	return false;
}

signed main(){
    cin >> n >> m >> k >> s; s++;
    p.resize(n+1); l.resize(n+1); chi.resize(n+1);in.resize(n+1), out.resize(n+1); sz.resize(n+1);
    l[0]=1;
    for(int i = 1; i <= n; i++){
        int dirr, lenn;
        cin >> dirr >> lenn;
        lenn++;
        p[i]=dirr;
        l[i]=lenn;
        chi[dirr].push_back(i);
    }
    dfs(0);
    for(int i = 0; i < m; i++){
        int dirr, lenn;
        cin >> dirr >> lenn;

        if(check(dirr, lenn)){
            cout << "YES\n";
        }
        else{
            cout << "NO\n";
        }
    }
}

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