Submission #104647

#	Time	Username	Problem	Language	Result	Execution time	Memory
104647		alexpetrescu	File Paths (BOI15_fil)	C++14	100 / 100	99 ms	1044 KiB

fil

#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, cnt;
bool ans[MAXN];
int G[MAXN], D[MAXN]; /// gauche, droite
int st[MAXN], r[MAXN], h[MAXN], v[MAXN];
std::vector < int > g[MAXN], e[MAXN];

bool cmp(const int &a, const int &b) {
    return h[a] < h[b];
}

inline bool check0(int x) { /// nu folosesc niciun symlink
    return k == (h[st[vf]] + x);
}

inline bool check1(int x) { /// folosesc un singur symlink
    /// conditia e sa existe i, j a.i. : k = l + x + h[st[vf]] - h[st[i]] + h[r[j]], 0 < i <= vf, 0 <= j <= n
    /// h[r[j]] = h[st[i]] + k - l - x - h[st[vf]]
    int j = 0;
    for (int i = 1; i <= vf; i++) {
        while (j <= n && h[r[j]] < h[st[i]] + k - l - x - h[st[vf]])
            j++;
        if (j <= n && h[r[j]] == h[st[i]] + k - l - x - h[st[vf]])
            return 1;
    }
    return 0;
}

inline bool stramos(int x, int y) { /// este x stramos al lui y?
    return G[x] <= G[y] && D[y] <= D[x];
}

inline bool solve(int x) {
    /// 0 <= i <= n, 0 < j <= vf, r[i] e in subarborele lui st[j], a.i. : x = l + h[r[i]] - h[st[j]]
    /// h[st[j]] = h[r[i]] + l - x
    int j = 1;
    for (int i = 0; i <= n; i++) {
        while (j <= vf && h[st[j]] < h[r[i]] + l - x)
            j++;
        if (j <= vf && h[st[j]] == h[r[i]] + l - x && stramos(st[j], r[i]))
            return 1;
    }
    return 0;
}

inline bool check2(int x) { /// folosesc mai multe symlinkuri
    /// conditia e sa existe i, j a.i. : (l + h[r[i]] - h[st[j]]) divide (k - x - h[st[vf]]), 0 <= i <= n, 0 < j <= vf, r[i] e in subarborele lui st[j]
    int q = k - x - h[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) {
    G[x] = ++cnt;
    for (auto &y : g[x]) {
        h[y] += h[x];
        dfs1(y);
    }
    D[x] = cnt;
}

void dfs2(int x) {
    st[++vf] = 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] = i;
    std::sort(r, r + n + 1, cmp);

    dfs2(0);

    for (int i = 0; i < m; i++)
        fputs(sir[ans[i]], fout);

    fclose(fin);
    fclose(fout);
    return 0;
}

Compilation message (stderr)

fil.cpp: In function 'int main()':
fil.cpp:93: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:98: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:106: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: 33 / 33
• Subtask 2: 33 / 33
• Subtask 3: 34 / 34