oj.uz

Submission #668666

# Submission time Handle Problem Language Result Execution time Memory
668666 2022-12-04T11:21:59 Z Kahou File Paths (BOI15_fil) C++14
33 / 100
 1000 ms 55884 KB 
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 6050;
int n, m, h[N], k, s, p[N];
vector<int> vc[N];
vector<int> vt[N];

void solve() {
	cin >> n >> m >> k;
	cin >> s;
	s++;
	vc[0].push_back(0);
	p[0] = -1;

	for (int u = 1; u <= n+m; u++) {
		int l;
		cin >> p[u] >> l;
		l++;

		h[u] = h[p[u]]+l;
		vc[u] = vc[p[u]];
		if (u <= n) vc[u].push_back(h[u]);
	}

	for (int u = 0; u <= n; u++) {
		int v = u;
		while (v >= 0) {
			vt[v].push_back(h[u]-h[v]+s);
			v = p[v];
		}
	}

	sort(h, h+n+1);
	for (int u = n+1; u <= n+m; u++) {
		bool flg = (h[u] == k);
		for (int x:vc[u]) {
			int v = lower_bound(h, h+n+1, k-s-(h[u]-x))-h;
			if (h[v] + s + h[u]-x == k) flg = 1;
		}
		int T = k- h[u];
		int v = u;
		while (v >= 0) {
			for (int d:vt[v]) {
				if (T%d == 0) flg = 1;
			}
			v = p[v];
		}
		cout << (flg? "YES":"NO") << endl;
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 101 ms 1748 KB Output is correct
5 Correct 9 ms 980 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 178 ms 2516 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 0 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 92 ms 1876 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 852 KB Output is correct
2 Correct 45 ms 960 KB Output is correct
3 Correct 44 ms 956 KB Output is correct
4 Correct 45 ms 960 KB Output is correct
5 Execution timed out 1096 ms 55884 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 101 ms 1748 KB Output is correct
5 Correct 9 ms 980 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 178 ms 2516 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 0 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 92 ms 1876 KB Output is correct
13 Correct 45 ms 852 KB Output is correct
14 Correct 45 ms 960 KB Output is correct
15 Correct 44 ms 956 KB Output is correct
16 Correct 45 ms 960 KB Output is correct
17 Execution timed out 1096 ms 55884 KB Time limit exceeded
18 Halted 0 ms 0 KB -