Submission #198301

#	Time	Username	Problem	Language	Result	Execution time	Memory
198301		dndhk	File Paths (BOI15_fil)	C++14	100 / 100	208 ms	26028 KiB

fil

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sort(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 6000;
const int MAX_K = 1000000;

int N, M, K, S;
int p[MAX_N+1], c[MAX_N+1];

vector<int> gp[MAX_N+1];
vector<int> vt[MAX_N+1];
bool chk[MAX_K+1];
int chk2[MAX_K+1];
bool ans[MAX_N+1];
int sum[MAX_N+1];

void dfs(int x){
	if(x!=0)sum[x] = sum[p[x]] + c[x] + 1;
	if(x<=N)	chk[sum[x]] = true;
	int t = p[x];
	while(x<=N){
		if(sum[x] - sum[t] + S + 1 <= K)	vt[t].pb(sum[x]-sum[t]+S+1);
		if(t==0)	break;
		t = p[t];
	}
	for(int i : gp[x]){
		dfs(i);
	}
}

void dfs2(int x){
	for(int t : vt[x]){
		chk2[t]++;
	}
	if(x>N){
		if(sum[x]==K){
			ans[x] = true;
		}else if(sum[x]<K){
			int t = p[x];
			while(1){
				int n = K-(sum[x]-sum[t]+S+1);
				if(n>=0 && n<=K){
					if(chk[n]){
						ans[x] = true;
						break;
					}
				}
				if(t==0)	break;
				t = p[t];
			}
			if(!ans[x]){
				int n = K - sum[x];
				for(int j=2; j*j<=n; j++){
					if(n%j==0){
						if(chk2[j]>0){
							ans[x] = true;
							break;
						}
						if(chk2[n/j]>0){
							ans[x] = true;
							break;
						}
					}
				}
			}
		}else{
			int t = p[x];
			while(1){
				int n = K - (sum[x]-sum[t]+S+1);
				if(n>=0 && n<=K){
					if(chk[n]){
						ans[x] = true;
						break;
					}
				}
				if(t==0)	break;
				t = p[t];
			}
		}
	}
	for(int i : gp[x]){
		dfs2(i);
	}
	for(int t : vt[x]){
		chk2[t]--;
	}
}

int main(){
	scanf("%d%d%d", &N, &M, &K);
	scanf("%d", &S);
	vt[0].pb(S+1);
	for(int i=1; i<=N; i++){
		scanf("%d%d", &p[i], &c[i]);
		gp[p[i]].pb(i);
	}
	for(int i=N+1; i<=N+M; i++){
		scanf("%d%d", &p[i], &c[i]);
		gp[p[i]].pb(i);
	}
	dfs(0);
	// for(int i=1; i<=N; i++){
	// 	printf("%d %d\n", i, sum[i]);
	// }
	dfs2(0);
	for(int i=N+1; i<=N+M; i++){
		if(ans[i]){
			printf("YES\n");
		}else{
			printf("NO\n");
		}
	}
	return 0;
}

Compilation message (stderr)

fil.cpp: In function 'int main()':
fil.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fil.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &S);
  ~~~~~^~~~~~~~~~
fil.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &p[i], &c[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fil.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &p[i], &c[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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