oj.uz

Submission #146117

# Submission time Handle Problem Language Result Execution time Memory
146117 2019-08-22T09:07:55 Z evpipis File Paths (BOI15_fil) C++11
100 / 100
 246 ms 74872 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
const int len = 1e6+5;
int n, m, k, s;
int cnt[len], sz[len], out[len], pre[len], dep[len], par[len];
vector<int> adj[len], vec, nex[len];

void add(int u, int t){
    for (int j = 0; j < nex[u].size(); j++)
        cnt[nex[u][j]] += t;

    if (t == 1){
        if (u == 0)
            vec.pb(0);
        else
            vec.pb(sz[u]+vec.back());
    }
    else{
        vec.pop_back();
    }
}

void fix(int u){
    pre[dep[u]]++;

    int p = u;
    while (true){
        nex[p].pb(dep[u]-dep[p]);

        if (p == 0)
            break;
        p = par[p];
    }

    for (int j = 0; j < adj[u].size(); j++){
        int v = adj[u][j];
        if (v > n) continue;

        dep[v] = dep[u]+sz[v];
        fix(v);
    }
}

void dfs(int u){
    if (u > n){
        int rem = k-(vec.back()+sz[u]);
        //printf("file: u = %d, rem = %d\n", u-n, rem);
        if (rem == 0)
            out[u-n] = 1;

        for (int i = 1; i*i <= rem; i++)
            if (rem%i == 0 && ((i-s >= 0 && cnt[i-s]) || (rem/i-s >= 0 && cnt[rem/i-s])))
                out[u-n] = 1;

        int sum = sz[u]+s;
        for (int i = (int)vec.size()-1; i >= 0; i--){
            if (k-sum >= 0 && pre[k-sum])
                out[u-n] = 1;

            if (i > 0)
                sum += vec[i]-vec[i-1];
        }

        return;
    }

    add(u, 1);
    for (int j = 0; j < adj[u].size(); j++){
        int v = adj[u][j];
        dfs(v);
    }
    add(u, -1);
}

int main(){
    scanf("%d %d %d %d", &n, &m, &k, &s);
    s++;

    for (int i = 1; i <= n; i++){
        scanf("%d %d", &par[i], &sz[i]);
        sz[i]++;
        adj[par[i]].pb(i);
    }

    for (int i = n+1; i <= n+m; i++){
        scanf("%d %d", &par[i], &sz[i]);
        sz[i]++;
        adj[par[i]].pb(i);
    }

    fix(0);
    dfs(0);

    for (int i = 1; i <= m; i++){
        if (out[i])
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

/*
3 1 10 2
0 1
1 1
2 1
0 2
*/

Compilation message

fil.cpp: In function 'void add(int, int)':
fil.cpp:11:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < nex[u].size(); j++)
                     ~~^~~~~~~~~~~~~~~
fil.cpp: In function 'void fix(int)':
fil.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
fil.cpp: In function 'void dfs(int)':
fil.cpp:70:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
fil.cpp: In function 'int main()':
fil.cpp:78:10: 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, &s);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fil.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &par[i], &sz[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fil.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &par[i], &sz[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 53 ms 47492 KB Output is correct
3 Correct 46 ms 48120 KB Output is correct
4 Correct 47 ms 48504 KB Output is correct
5 Correct 56 ms 52344 KB Output is correct
6 Correct 50 ms 50808 KB Output is correct
7 Correct 55 ms 53880 KB Output is correct
8 Correct 51 ms 52088 KB Output is correct
9 Correct 50 ms 51960 KB Output is correct
10 Correct 45 ms 47352 KB Output is correct
11 Correct 45 ms 47352 KB Output is correct
12 Correct 47 ms 48376 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 54520 KB Output is correct
2 Correct 57 ms 54524 KB Output is correct
3 Correct 57 ms 54520 KB Output is correct
4 Correct 57 ms 54520 KB Output is correct
5 Correct 208 ms 74760 KB Output is correct
6 Correct 212 ms 74848 KB Output is correct
7 Correct 125 ms 64600 KB Output is correct
8 Correct 126 ms 64760 KB Output is correct
9 Correct 58 ms 54264 KB Output is correct
10 Correct 58 ms 54052 KB Output is correct
11 Correct 50 ms 48376 KB Output is correct
12 Correct 195 ms 69340 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 53 ms 47492 KB Output is correct
3 Correct 46 ms 48120 KB Output is correct
4 Correct 47 ms 48504 KB Output is correct
5 Correct 56 ms 52344 KB Output is correct
6 Correct 50 ms 50808 KB Output is correct
7 Correct 55 ms 53880 KB Output is correct
8 Correct 51 ms 52088 KB Output is correct
9 Correct 50 ms 51960 KB Output is correct
10 Correct 45 ms 47352 KB Output is correct
11 Correct 45 ms 47352 KB Output is correct
12 Correct 47 ms 48376 KB Output is correct
13 Correct 56 ms 54520 KB Output is correct
14 Correct 57 ms 54524 KB Output is correct
15 Correct 57 ms 54520 KB Output is correct
16 Correct 57 ms 54520 KB Output is correct
17 Correct 208 ms 74760 KB Output is correct
18 Correct 212 ms 74848 KB Output is correct
19 Correct 125 ms 64600 KB Output is correct
20 Correct 126 ms 64760 KB Output is correct
21 Correct 58 ms 54264 KB Output is correct
22 Correct 58 ms 54052 KB Output is correct
23 Correct 50 ms 48376 KB Output is correct
24 Correct 195 ms 69340 KB Output is correct
25 Correct 58 ms 54520 KB Output is correct
26 Correct 57 ms 54520 KB Output is correct
27 Correct 56 ms 54544 KB Output is correct
28 Correct 58 ms 54532 KB Output is correct
29 Correct 212 ms 74744 KB Output is correct
30 Correct 211 ms 74872 KB Output is correct
31 Correct 125 ms 64852 KB Output is correct
32 Correct 123 ms 64708 KB Output is correct
33 Correct 64 ms 54136 KB Output is correct
34 Correct 56 ms 54136 KB Output is correct
35 Correct 51 ms 48248 KB Output is correct
36 Correct 246 ms 73184 KB Output is correct