oj.uz

Submission #78986

# Submission time Handle Problem Language Result Execution time Memory
78986 2018-10-10T06:14:49 Z win11905 Ball Machine (BOI13_ballmachine) C++11
0 / 100
 155 ms 28348 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define x first
#define y second

const int N = 1e5+5;

int n, m;
int par[N][17], dep[N];
vector<int> g[N];
vector<pii> ng[N];

int dfs(int u) {
    int mn = u;
    for(int i = 1; i < 17; ++i) par[u][i] = par[par[u][i-1]][i-1];
    for(int v : g[u]) {
        dep[v] = dep[u] + 1, par[v][0] = u;
        int now = dfs(v); 
        mn = min(mn, now);
        ng[u].emplace_back(mn, v);
    }
    sort(ng[u].begin(), ng[u].end());
    return mn;
}

int A[N], ptr;
int pos[N];
int block = 320;
int sz[350];
bool d[N];
pii t[350];


void solve(int u) {
    for(auto v : ng[u]) solve(v.y);
    A[ptr++] = u;
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1, val; i <= n; ++i) scanf("%d", &val), g[val].emplace_back(i);
    dep[1] = 1, dfs(1);
    solve(1);
    for(int i = 0; i < n; ++i) sz[i/block]++;
    int last = n / block;
    for(int i = 1; i <= n; ++i) pos[A[i]] = i;
    for(int i = 0, a, b; i < m; ++i) {
        scanf("%d %d", &a, &b);
        if(a == 1) {
            for(int i = 0; i <= last; ++i) {
                if(b - (sz[i] - t[i].x) > 0) b -= sz[i] - t[i].x, t[i] = pii(sz[i], 1);
                else {
                    assert(t[i].y == 0);
                    t[i] = pii(0, 0);
                    for(int j = i * block; j < i * block + sz[i]; ++j) {
                        if(d[j]) t[i].x++;
                        else if(b--) d[j] = true, t[i].x++;
                        if(!b) {
                            printf("%d\n", A[j]);
                            break;
                        }
                    }
                    break;
                } 
            } 
        } else {
            auto check = [&](int v) {
                if(t[pos[v]/block].y) return true;
                else if(d[pos[v]]) return true;
            };
            int sum = 0;
            for(int i = 16; ~i; --i) 
                if(check(par[b][i])) b = par[b][i], sum += 1<<i;
            printf("%d\n", sum);
            b = pos[b];
            int ith = b / block;
            if(t[ith].y) for(int j = ith * block; j < ith * block + sz[ith]; ++j) d[j] = 1;
            d[b] = 0;
            t[ith] = pii(0, 0);
            for(int j = ith * block; j < ith * block + sz[ith]; ++j) 
                t[ith].x += d[j]; 
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:43:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1, val; i <= n; ++i) scanf("%d", &val), g[val].emplace_back(i);
                                      ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp: In lambda function:
ballmachine.cpp:72:13: warning: control reaches end of non-void function [-Wreturn-type]
             };
             ^

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 KB Output isn't correct
2 Incorrect 79 ms 6900 KB Output isn't correct
3 Incorrect 91 ms 6900 KB Output isn't correct
4 Incorrect 5 ms 6900 KB Output isn't correct
5 Incorrect 6 ms 6900 KB Output isn't correct
6 Incorrect 6 ms 6900 KB Output isn't correct
7 Incorrect 6 ms 6900 KB Output isn't correct
8 Incorrect 6 ms 6900 KB Output isn't correct
9 Incorrect 11 ms 6900 KB Output isn't correct
10 Incorrect 19 ms 6900 KB Output isn't correct
11 Incorrect 80 ms 7248 KB Output isn't correct
12 Incorrect 91 ms 7248 KB Output isn't correct
13 Incorrect 80 ms 7248 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 10284 KB Output isn't correct
2 Incorrect 101 ms 18656 KB Output isn't correct
3 Incorrect 93 ms 18656 KB Output isn't correct
4 Incorrect 62 ms 18656 KB Output isn't correct
5 Incorrect 52 ms 18656 KB Output isn't correct
6 Incorrect 55 ms 18656 KB Output isn't correct
7 Incorrect 52 ms 18656 KB Output isn't correct
8 Incorrect 60 ms 18656 KB Output isn't correct
9 Incorrect 127 ms 23916 KB Output isn't correct
10 Incorrect 105 ms 23916 KB Output isn't correct
11 Incorrect 81 ms 23916 KB Output isn't correct
12 Incorrect 86 ms 23916 KB Output isn't correct
13 Incorrect 124 ms 23916 KB Output isn't correct
14 Incorrect 91 ms 23916 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 23916 KB Output isn't correct
2 Incorrect 116 ms 23916 KB Output isn't correct
3 Incorrect 74 ms 23916 KB Output isn't correct
4 Incorrect 54 ms 23916 KB Output isn't correct
5 Incorrect 53 ms 23916 KB Output isn't correct
6 Incorrect 57 ms 23916 KB Output isn't correct
7 Incorrect 72 ms 23916 KB Output isn't correct
8 Incorrect 73 ms 23916 KB Output isn't correct
9 Incorrect 87 ms 23916 KB Output isn't correct
10 Incorrect 115 ms 23916 KB Output isn't correct
11 Incorrect 105 ms 23916 KB Output isn't correct
12 Incorrect 118 ms 23916 KB Output isn't correct
13 Incorrect 113 ms 23916 KB Output isn't correct
14 Incorrect 91 ms 23916 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 23916 KB Output isn't correct
2 Incorrect 133 ms 23916 KB Output isn't correct
3 Incorrect 155 ms 28348 KB Output isn't correct
4 Incorrect 91 ms 28348 KB Output isn't correct
5 Incorrect 92 ms 28348 KB Output isn't correct
6 Incorrect 141 ms 28348 KB Output isn't correct
7 Incorrect 126 ms 28348 KB Output isn't correct
8 Incorrect 149 ms 28348 KB Output isn't correct
9 Incorrect 100 ms 28348 KB Output isn't correct