Submission #31338

#	Time	Username	Problem	Language	Result	Execution time	Memory
31338		imaxblue	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	399 ms	32444 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)

int n, m, r, p, t, x, c=0;
int a[100005], o[100005], d[100005], sub[100005], sp[20][100005];
bool u[100005];
vector<int> v[100005];
set<pii> s;
void dfs(int N, int P){
    sub[N]=N;
    sp[0][N]=P;
    if (P==-1) d[P]=0;
    else d[N]=d[P]+1;
    fox1(l, 18){
        if (sp[l-1][N]==-1) sp[l][N]=-1;
        else sp[l][N]=sp[l-1][sp[l-1][N]];
    }
    //cout << N << ": \n";
    //fox(l, 4) cout << sp[l][N] << ' '; cout << endl;
    fox(l, v[N].size()){
        dfs(v[N][l], N);
        sub[N]=min(sub[N], sub[v[N][l]]);
    }
}
void dfs2(int N){
    vector<pii> ord;
    fox(l, v[N].size()){
        ord.pb(mp(sub[v[N][l]], v[N][l]));
    }
    sort(ord.begin(), ord.end());
    fox(l, ord.size()){
        dfs2(ord[l].y);
    }
    o[N]=++c;
    s.insert(mp(o[N], N));
}
int an(int X){
    int k=18;
    while(k>0){
        while(k>0 && (sp[k][X]==-1 || !u[sp[k][X]])){
            k--;
        }
        if (sp[k][X]==-1 || !u[sp[k][X]]) break;
        X=sp[k][X];
    }
    s.insert(mp(o[X], X));
    u[X]=0;
    //cout << X << ' ' << d[X] << endl;
    return d[X];
}
int main(){
    scanf("%i%i", &n, &m);
    fox1(l, n){
        scanf("%i", &p);
        v[p].pb(l);
    }
    dfs(0, -1);
    dfs2(0);
    c=0;
    fox(l, m){
        scanf("%i%i", &t, &x);
        if (t==1){
            fox(l2, x){
                u[s.begin()->y]=1;
                t=s.begin()->y;
                s.erase(s.begin());
            }
            printf("%i\n", t);
        } else {
            //cout << x << ' ';
            printf("%i\n", d[x]-an(x));
        }
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs(int, int)':
ballmachine.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
ballmachine.cpp:42:5: note: in expansion of macro 'fox'
     fox(l, v[N].size()){
     ^
ballmachine.cpp: In function 'void dfs2(int)':
ballmachine.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
ballmachine.cpp:49:5: note: in expansion of macro 'fox'
     fox(l, v[N].size()){
     ^
ballmachine.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
ballmachine.cpp:53:5: note: in expansion of macro 'fox'
     fox(l, ord.size()){
     ^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:74:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i", &n, &m);
                          ^
ballmachine.cpp:76:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i", &p);
                        ^
ballmachine.cpp:83:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i", &t, &x);
                              ^
ballmachine.cpp: In function 'void dfs(int, int)':
ballmachine.cpp:34:19: warning: array subscript is below array bounds [-Warray-bounds]
     if (P==-1) d[P]=0;
                   ^

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5