# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
104634 | alexpetrescu | File Paths (BOI15_fil) | C++14 | 42 ms | 900 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <algorithm>
#include <vector>
//FILE *fin = fopen("a.in", "r"), *fout = fopen("a.out", "w");
#define fin stdin
#define fout stdout
#define MAXN 3009
char sir[2][5] = {
{
'N', 'O', '\n', '\0', '\0'
},
{
'Y', 'E', 'S', '\n', '\0'
}
};
int n, k, l, vf;
bool ans[MAXN];
int st[MAXN], r[MAXN], h[MAXN], v[MAXN];
std::vector < int > g[MAXN], e[MAXN];
inline bool check0(int x) { /// nu folosesc niciun symlink
return k == (st[vf] + x);
}
inline bool check1(int x) { /// folosesc un singur symlink
/// conditia e sa existe i, j a.i. : k = l + x + st[vf] - st[i] + r[j], 0 < i <= vf, 0 <= j <= n
/// r[j] = st[i] + k - l - x - st[vf]
int j = 0;
for (int i = 1; i <= vf; i++) {
while (j <= n && r[j] < st[i] + k - l - x - st[vf])
j++;
if (j <= n && r[j] == st[i] + k - l - x - st[vf])
return 1;
}
return 0;
}
inline bool solve(int x) {
/// cautam 0 < i <= j <= vf a.i. : x = l + st[j] - st[i]
/// st[j] = st[i] + x - l
int j = 1;
for (int i = 1; i <= vf; i++) {
while (j <= vf && (j < i || st[j] < st[i] + x - l))
j++;
if (j <= vf && st[j] == st[i] + x - l)
return 1;
}
return 0;
}
inline bool check2(int x) { /// folosesc mai multe symlinkuri
/// conditia e sa existe i, j a.i. : (l + st[j] - st[i]) divide (k - x - st[vf]), 0 < i <= j <= vf
int q = k - x - st[vf];
for (int i = 1; i * i <= q; i++)
if (q % i == 0 && (solve(i) || solve(q / i)))
return 1;
return 0;
}
void dfs1(int x) {
for (auto &y : g[x]) {
h[y] += h[x];
dfs1(y);
}
}
void dfs2(int x) {
st[++vf] = h[x];
for (auto &y : g[x])
dfs2(y);
for (auto &y : e[x])
ans[y] = (check0(v[y]) || check1(v[y]) || check2(v[y]));
vf--;
}
int main() {
int m;
fscanf(fin, "%d%d%d%d", &n, &m, &k, &l);
l++;
for (int i = 1; i <= n; i++) {
int x;
fscanf(fin, "%d%d", &x, &h[i]);
h[i]++;
g[x].push_back(i);
}
for (int i = 0; i < m; i++) {
int x;
fscanf(fin, "%d%d", &x, &v[i]);
v[i]++;
e[x].push_back(i);
}
dfs1(0);
for (int i = 0; i <= n; i++)
r[i] = h[i];
std::sort(r, r + n + 1);
dfs2(0);
for (int i = 0; i < m; i++)
fputs(sir[ans[i]], fout);
fclose(fin);
fclose(fout);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |