제출 #1173106

#제출 시각아이디문제언어결과실행 시간메모리
1173106ThommyDBFile Paths (BOI15_fil)C++20
0 / 100
1096 ms580 KiB
#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 1;
	
    for(int i = 1; i <= n; i++){
        for(int j = 1; 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";
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...