Submission #200608

#	Time	Username	Problem	Language	Result	Execution time	Memory
200608		TadijaSebez	File Paths (BOI15_fil)	C++11	100 / 100	305 ms	8252 KiB

fil

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=6050;
const int K=2000050;
int par[N],len[N],dep[N],n,m,k,s;
bool ok[N];
vector<int> E[N];
int can[K],cyc[K];
void Add(int u,int f,int p){
	if(u<=n)cyc[dep[u]-dep[p]+s+1]+=f;
	for(int v:E[u])Add(v,f,p);
}
void DFS(int u){
	if(u>n){
		int tmp=k-dep[u];
		if(tmp==0)ok[u]=1;
		for(int i=1;i*i<=tmp;i++)if(tmp%i==0){
			if(cyc[i]||cyc[tmp/i])ok[u]=1;
		}
		for(int v=par[u];v!=-1;v=par[v]){
			if(k-dep[u]+dep[v]-s-1<0)continue;
			if(can[k-dep[u]+dep[v]-s-1])ok[u]=1;
		}
	}else{
		for(int v=u;v!=-1;v=par[v]){
			cyc[dep[u]-dep[v]+s+1]++;
		}
		Add(u,1,u);
	}
	for(int v:E[u])DFS(v);
	if(u<=n){
		for(int v=u;v!=-1;v=par[v]){
			cyc[dep[u]-dep[v]+s+1]--;
		}
		Add(u,-1,u);
	}
}
int main(){
	scanf("%i %i %i %i",&n,&m,&k,&s);
	dep[0]=0;par[0]=-1;can[0]=1;
	for(int i=1;i<=n+m;i++){
		scanf("%i %i",&par[i],&len[i]);
		E[par[i]].pb(i);
		dep[i]=dep[par[i]]+len[i]+1;
		if(i<=n && dep[i]<K)can[dep[i]]++;
	}
	for(int i=0;i<=n;i++)cyc[dep[i]+s+1]++;
	DFS(0);
	for(int i=n+1;i<=n+m;i++)printf("%s\n",ok[i]?"YES":"NO");
	return 0;
}

Compilation message (stderr)

fil.cpp: In function 'int main()':
fil.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i %i",&n,&m,&k,&s);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
fil.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&par[i],&len[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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