oj.uz

답안 #666899

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
666899 2022-11-29T21:33:07 Z mmk Ball Machine (BOI13_ballmachine) C++14
0 / 100
 36 ms 16396 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+10;
int n,raiz;
int pai[MAXN],cap[MAXN],menor[MAXN];
vector<int> filhos[MAXN];
void build(int v)
{
    if(filhos[v].size() == 0)
    {
        cap[v] = 1;
        menor[v] = v;
        return;
    }
    build(filhos[v][0]);
    build(filhos[v][1]);
    menor[v] = min(menor[filhos[v][0]],menor[filhos[v][1]]);
    menor[v] = min(v,menor[v]);
    cap[v] = cap[filhos[v][0]] + cap[filhos[v][1]]+1;
}
void update1(int id)
{
    cap[id] = 0;
    if(filhos[id].size() == 0) return;
    update1(filhos[id][0]);
    update1(filhos[id][1]);
}
int query1(int id,int k)
{
    //cerr << cap[id] << " " << id << "\n";
    if(cap[id] == k)
    {
        update1(id);
        return id;
    }
    cap[id] -= k;
    int f1,f2;
    f1 = filhos[id][0];
    f2 = filhos[id][1];
    if(menor[f1] < menor[f2])
    {
        if(cap[f1] == k)
        {
            update1(f1);
            return f1;
        }
        if(cap[f1] > k)
        {
            return query1(f1,k);
        }
        else
        {
            int aux = cap[f1];
            update1(f1);
            return query1(f2,k-cap[f1]);
        }
    }
    else if(menor[f1] > menor[f2])
    {
        if(cap[f2] == k)
        {
            update1(f2);
            return f2;
        }
        if(cap[f2] > k)
        {
            cap[f2] -= k;
            return query1(f2,k);
        }
        else
        {
            int aux = cap[f2];
            update1(f2);
            return query1(f1,k-cap[f2]);
        }
    }
}
int query2(int id,int cont)
{
    //cerr << id << " " << cont << "\n";
    cap[id]++;
    if(pai[id] == id) return cont;
    if(cap[pai[id]] > 0) return cont;
    return query2(pai[id],cont+1);
}
void update2(int id)
{
    cap[id]++;
    if(pai[id] == id) return;
    update2(pai[id]);
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int q;
    cin >> n >> q;
    for(int i = 0; i < n; i++)
    {
        int aux;
        cin >> aux;
        if(aux == 0)
        {
            raiz = i;
            pai[i] = i;
        }
        else
        {
            pai[i] = aux;
            filhos[aux].push_back(i);
        }
    }
    build(raiz);
    for(int i = 0; i < q; i++)
    {
        //cerr << "||" << cap[raiz] << "\n";
        int a,b;
        cin >> a >> b;
        if(a == 1)
             cout << query1(raiz,b) << "\n";
        else
        {
            cout << query2(b,0) << "\n";
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int query1(int, int)':
ballmachine.cpp:53:17: warning: unused variable 'aux' [-Wunused-variable]
   53 |             int aux = cap[f1];
      |                 ^~~
ballmachine.cpp:72:17: warning: unused variable 'aux' [-Wunused-variable]
   72 |             int aux = cap[f2];
      |                 ^~~
ballmachine.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
   77 | }
      | ^

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 5204 KB Execution killed with signal 11
2 Runtime error 13 ms 7892 KB Execution killed with signal 11
3 Runtime error 13 ms 8320 KB Execution killed with signal 11
4 Runtime error 4 ms 5168 KB Execution killed with signal 11
5 Runtime error 4 ms 5140 KB Execution killed with signal 11
6 Runtime error 4 ms 5204 KB Execution killed with signal 11
7 Runtime error 5 ms 5268 KB Execution killed with signal 11
8 Runtime error 4 ms 5204 KB Execution killed with signal 11
9 Runtime error 5 ms 5460 KB Execution killed with signal 11
10 Runtime error 6 ms 5972 KB Execution killed with signal 11
11 Runtime error 20 ms 7820 KB Execution killed with signal 11
12 Runtime error 14 ms 8276 KB Execution killed with signal 11
13 Runtime error 14 ms 8148 KB Execution killed with signal 11

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 6900 KB Execution killed with signal 11
2 Runtime error 18 ms 9940 KB Execution killed with signal 11
3 Runtime error 16 ms 8860 KB Execution killed with signal 11
4 Runtime error 12 ms 6868 KB Execution killed with signal 11
5 Runtime error 10 ms 6740 KB Execution killed with signal 11
6 Runtime error 8 ms 6612 KB Execution killed with signal 11
7 Runtime error 15 ms 6868 KB Execution killed with signal 11
8 Runtime error 8 ms 6868 KB Execution killed with signal 11
9 Runtime error 21 ms 10876 KB Execution killed with signal 11
10 Runtime error 19 ms 9932 KB Execution killed with signal 11
11 Runtime error 19 ms 10068 KB Execution killed with signal 11
12 Runtime error 21 ms 10084 KB Execution killed with signal 11
13 Runtime error 31 ms 16396 KB Execution killed with signal 11
14 Runtime error 17 ms 8848 KB Execution killed with signal 11

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 8200 KB Execution killed with signal 11
2 Runtime error 18 ms 10024 KB Execution killed with signal 11
3 Runtime error 17 ms 12240 KB Execution killed with signal 11
4 Runtime error 21 ms 9696 KB Execution killed with signal 11
5 Runtime error 23 ms 9044 KB Execution killed with signal 11
6 Runtime error 16 ms 9004 KB Execution killed with signal 11
7 Runtime error 17 ms 9812 KB Execution killed with signal 11
8 Runtime error 17 ms 12244 KB Execution killed with signal 11
9 Runtime error 26 ms 10736 KB Execution killed with signal 11
10 Runtime error 21 ms 9940 KB Execution killed with signal 11
11 Runtime error 20 ms 10068 KB Execution killed with signal 11
12 Runtime error 24 ms 9900 KB Execution killed with signal 11
13 Runtime error 21 ms 14140 KB Execution killed with signal 11
14 Runtime error 18 ms 8872 KB Execution killed with signal 11

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 10816 KB Execution killed with signal 11
2 Runtime error 18 ms 9940 KB Execution killed with signal 11
3 Runtime error 36 ms 15404 KB Execution killed with signal 11
4 Runtime error 19 ms 10868 KB Execution killed with signal 11
5 Runtime error 20 ms 10136 KB Execution killed with signal 11
6 Runtime error 19 ms 10132 KB Execution killed with signal 11
7 Runtime error 20 ms 9976 KB Execution killed with signal 11
8 Runtime error 27 ms 15464 KB Execution killed with signal 11
9 Runtime error 16 ms 8768 KB Execution killed with signal 11