oj.uz

Submission #104634

# Submission time Handle Problem Language Result Execution time Memory
104634 2019-04-08T13:06:31 Z alexpetrescu File Paths (BOI15_fil) C++14
33 / 100
 42 ms 900 KB 
#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

fil.cpp: In function 'int main()':
fil.cpp:82:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fin, "%d%d%d%d", &n, &m, &k, &l);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fil.cpp:87:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(fin, "%d%d", &x, &h[i]);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fil.cpp:95:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(fin, "%d%d", &x, &v[i]);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 640 KB Output is correct
2 Correct 10 ms 668 KB Output is correct
3 Correct 12 ms 640 KB Output is correct
4 Correct 14 ms 640 KB Output is correct
5 Correct 32 ms 900 KB Output is correct
6 Correct 20 ms 896 KB Output is correct
7 Correct 42 ms 768 KB Output is correct
8 Correct 30 ms 768 KB Output is correct
9 Correct 14 ms 640 KB Output is correct
10 Correct 11 ms 640 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Correct 30 ms 896 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -