oj.uz

Submission #78984

# Submission time Handle Problem Language Result Execution time Memory
78984 2018-10-10T05:48:19 Z win11905 Ball Machine (BOI13_ballmachine) C++11
0 / 100
 167 ms 74132 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 = 1; 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) t[i] = pii(sz[i], 1), b -= sz[i] - t[i].x;
                else {
                    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:71: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 5112 KB Output isn't correct
2 Incorrect 87 ms 8116 KB Output isn't correct
3 Incorrect 94 ms 8956 KB Output isn't correct
4 Incorrect 6 ms 8956 KB Output isn't correct
5 Incorrect 6 ms 8956 KB Output isn't correct
6 Incorrect 6 ms 8956 KB Output isn't correct
7 Incorrect 7 ms 8956 KB Output isn't correct
8 Incorrect 8 ms 8956 KB Output isn't correct
9 Incorrect 12 ms 8956 KB Output isn't correct
10 Incorrect 32 ms 8956 KB Output isn't correct
11 Incorrect 90 ms 10864 KB Output isn't correct
12 Incorrect 96 ms 11544 KB Output isn't correct
13 Incorrect 103 ms 12776 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 16608 KB Output isn't correct
2 Incorrect 126 ms 26156 KB Output isn't correct
3 Incorrect 98 ms 26156 KB Output isn't correct
4 Incorrect 62 ms 26156 KB Output isn't correct
5 Incorrect 54 ms 26156 KB Output isn't correct
6 Incorrect 59 ms 26156 KB Output isn't correct
7 Incorrect 63 ms 26156 KB Output isn't correct
8 Incorrect 61 ms 26156 KB Output isn't correct
9 Incorrect 143 ms 37332 KB Output isn't correct
10 Incorrect 133 ms 37332 KB Output isn't correct
11 Incorrect 89 ms 37332 KB Output isn't correct
12 Incorrect 93 ms 37332 KB Output isn't correct
13 Incorrect 128 ms 37476 KB Output isn't correct
14 Incorrect 102 ms 37476 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 37476 KB Output isn't correct
2 Incorrect 134 ms 40144 KB Output isn't correct
3 Incorrect 79 ms 40184 KB Output isn't correct
4 Incorrect 68 ms 40184 KB Output isn't correct
5 Incorrect 62 ms 40184 KB Output isn't correct
6 Incorrect 55 ms 40184 KB Output isn't correct
7 Incorrect 91 ms 42456 KB Output isn't correct
8 Incorrect 101 ms 44784 KB Output isn't correct
9 Incorrect 106 ms 44784 KB Output isn't correct
10 Incorrect 95 ms 44784 KB Output isn't correct
11 Incorrect 123 ms 48176 KB Output isn't correct
12 Incorrect 145 ms 50996 KB Output isn't correct
13 Incorrect 126 ms 53428 KB Output isn't correct
14 Incorrect 83 ms 53428 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 53428 KB Output isn't correct
2 Incorrect 142 ms 57552 KB Output isn't correct
3 Incorrect 162 ms 67436 KB Output isn't correct
4 Incorrect 97 ms 67436 KB Output isn't correct
5 Incorrect 100 ms 67436 KB Output isn't correct
6 Incorrect 148 ms 67436 KB Output isn't correct
7 Incorrect 130 ms 67436 KB Output isn't correct
8 Incorrect 167 ms 74132 KB Output isn't correct
9 Incorrect 94 ms 74132 KB Output isn't correct