oj.uz

Submission #22990

# Submission time Handle Problem Language Result Execution time Memory
22990 2017-05-01T02:55:16 Z model_code File Paths (BOI15_fil) C++11
33 / 100
 1000 ms 2148 KB 
// Tomasz Syposz, O(n^2 m)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=(a);i<=(b);++i)
#define FORI(i,n) REP(i,1,n)
#define FOR(i,n) REP(i,0,int(n)-1)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define SZ(x) int((x).size())
#define DBG(v) cerr << #v << " = " << (v) << endl;
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define SORT(X) sort(X.begin(),X.end())
#define fi first
#define se second

int Oj[3030];
int L[3030];
vector<int> V[3030];

int Sd[3030];
int In[3030];
int Out[3030];
int T,tmp_sd;

void dfs(int u){
	In[u] = ++T;
	tmp_sd += L[u];
	FOR(i,SZ(V[u]))
		dfs(V[u][i]);
	
	Sd[u] = tmp_sd;
	Out[u] = ++T;
	tmp_sd -= L[u];
//	printf("%d: %d %d %d\n", u,Sd[u],In[u],Out[u]);
}

int mxLen,slink,n;

bool below(int a, int b){
	if(In[a] > In[b]) return 0;
	if(Out[a] < Out[b]) return 0;
	return 1;
}

bool check(int a,int b){
//	cout<<Sd[a]+b<<endl;
	if(Sd[a] + b == mxLen) return 1;
	
	FOR(i,n+1) FOR(j,n+1){
		if(!below(j,a)) continue;
		if(Sd[a]+Sd[i]-Sd[j]+slink+b == mxLen) return 1;
		if(!below(j,i)) continue;
		if((mxLen - b-Sd[a]) % (slink+Sd[i]-Sd[j]) == 0) return 1;
	}
	return 0;
}

int main () {
	int m,k;
	scanf("%d%d%d%d",&n,&m,&k,&slink);
	mxLen = k;
	slink++;
	FORI(i,n){
		int a,b;
		scanf("%d%d",&a,&b);
		Oj[i] = a;
		L[i] = b+1;
		V[a].pb(i);
	}
	L[0] = 1;
	dfs(0);
	FOR(i,m){
		int a,b;
		scanf("%d%d",&a,&b);
		
		bool IF = check(a,b);

		if(IF) puts("YES");
		else puts("NO");
	}
}

Compilation message

fil.cpp: In function 'int main()':
fil.cpp:64:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&n,&m,&k,&slink);
                                   ^
fil.cpp:69:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
                      ^
fil.cpp:78:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
                      ^

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2148 KB Output is correct
2 Correct 123 ms 2148 KB Output is correct
3 Correct 286 ms 2148 KB Output is correct
4 Correct 129 ms 2148 KB Output is correct
5 Correct 333 ms 2148 KB Output is correct
6 Correct 329 ms 2148 KB Output is correct
7 Correct 193 ms 2148 KB Output is correct
8 Correct 339 ms 2148 KB Output is correct
9 Correct 306 ms 2148 KB Output is correct
10 Correct 0 ms 2148 KB Output is correct
11 Correct 176 ms 2148 KB Output is correct
12 Correct 96 ms 2148 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 2148 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2148 KB Output is correct
2 Correct 123 ms 2148 KB Output is correct
3 Correct 286 ms 2148 KB Output is correct
4 Correct 129 ms 2148 KB Output is correct
5 Correct 333 ms 2148 KB Output is correct
6 Correct 329 ms 2148 KB Output is correct
7 Correct 193 ms 2148 KB Output is correct
8 Correct 339 ms 2148 KB Output is correct
9 Correct 306 ms 2148 KB Output is correct
10 Correct 0 ms 2148 KB Output is correct
11 Correct 176 ms 2148 KB Output is correct
12 Correct 96 ms 2148 KB Output is correct
13 Execution timed out 1000 ms 2148 KB Execution timed out
14 Halted 0 ms 0 KB -