Submission #1173129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173129		ThommyDB	File Paths (BOI15_fil)	C++20	100 / 100	111 ms	9136 KiB

fil

#include <bits/stdc++.h>

using namespace std;

int n,m,k,s;
vector<int> cyc, l, D, path;
vector<bool> hasl;
vector<vector<int>> chi;
vector<pair<int, bool>> ans;
vector<vector<pair<int, int>>> file;

void dfill(int a){
	D.clear();
	for(int i = 1; i*i <= a; i++) if(a%i==0){
		D.push_back(i);
		D.push_back(a/i);
	}
}

void update(int u, int Ld, int w){
    cyc[l[u]-Ld+s] += w;
    for(int v = 0; v < chi[u].size(); v++){
        update(chi[u][v],Ld,w);
    }
}

void solve(int u){
	path.push_back(u);
	update(u,l[u],1);
    for(int z = 0; z < file[u].size(); z++){
        dfill(k - l[u] - file[u][z].first);
        bool anss = false;
        for(int d = 0; d < D.size(); d++){
            if(cyc[D[d]] > 0) anss = true;
        }
        for(int p = 0; p < path.size(); p++){
            if(k - (l[u]-l[path[p]]+s+file[u][z].first) >= 0 && hasl[k - (l[u]-l[path[p]]+s+file[u][z].first)]) anss = true;
        }
        if(l[u]+file[u][z].first == k) anss = true;
		ans.push_back({file[u][z].second,anss});
    }
    for(int v = 0; v < chi[u].size(); v++){
        solve(chi[u][v]);
    }
	path.pop_back();
	update(u,l[u],-1);
}

int main () {
	cin >> n >> m >> k >> s;
    chi.resize(n+1); file.resize(n+1); cyc.resize(2000001); l.resize(n+1); hasl.resize(1000001);
	s++;
	k = k;
	l[0] = 1;
	hasl[1] = true;
    for(int i = 1; i <= n; i++){
        int a,b;
		cin >> a >> b;
		l[i] = b+1+l[a];
		hasl[l[i]] = true;
		chi[a].push_back(i);
    }

    for(int i = 0; i < m; i++){
        int a,b;
		cin >> a >> b;
		file[a].push_back({b,i});
    }
	solve(0);
	sort(ans.begin(), ans.end());
    for(auto u : ans){
        cout << (u.second?"YES\n":"NO\n");
    }
}

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