oj.uz

Submission #31338

# Submission time Handle Problem Language Result Execution time Memory
31338 2017-08-18T20:21:14 Z imaxblue Ball Machine (BOI13_ballmachine) C++14
100 / 100
 399 ms 32444 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13844 KB Output is correct
2 Correct 206 ms 17936 KB Output is correct
3 Correct 133 ms 17936 KB Output is correct
4 Correct 0 ms 13844 KB Output is correct
5 Correct 0 ms 13844 KB Output is correct
6 Correct 3 ms 13976 KB Output is correct
7 Correct 3 ms 13976 KB Output is correct
8 Correct 3 ms 13976 KB Output is correct
9 Correct 9 ms 14108 KB Output is correct
10 Correct 33 ms 14900 KB Output is correct
11 Correct 253 ms 17936 KB Output is correct
12 Correct 116 ms 17936 KB Output is correct
13 Correct 166 ms 17936 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 17164 KB Output is correct
2 Correct 286 ms 25912 KB Output is correct
3 Correct 139 ms 20480 KB Output is correct
4 Correct 149 ms 17468 KB Output is correct
5 Correct 93 ms 17332 KB Output is correct
6 Correct 136 ms 17340 KB Output is correct
7 Correct 123 ms 16324 KB Output is correct
8 Correct 46 ms 17172 KB Output is correct
9 Correct 253 ms 26316 KB Output is correct
10 Correct 303 ms 25908 KB Output is correct
11 Correct 259 ms 25920 KB Output is correct
12 Correct 289 ms 22992 KB Output is correct
13 Correct 166 ms 30232 KB Output is correct
14 Correct 133 ms 20480 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 20016 KB Output is correct
2 Correct 386 ms 23188 KB Output is correct
3 Correct 209 ms 28672 KB Output is correct
4 Correct 196 ms 23772 KB Output is correct
5 Correct 229 ms 23504 KB Output is correct
6 Correct 219 ms 23504 KB Output is correct
7 Correct 209 ms 21320 KB Output is correct
8 Correct 219 ms 28676 KB Output is correct
9 Correct 346 ms 26320 KB Output is correct
10 Correct 373 ms 25924 KB Output is correct
11 Correct 359 ms 25920 KB Output is correct
12 Correct 369 ms 23184 KB Output is correct
13 Correct 399 ms 32444 KB Output is correct
14 Correct 276 ms 20484 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 26316 KB Output is correct
2 Correct 323 ms 23184 KB Output is correct
3 Correct 206 ms 32444 KB Output is correct
4 Correct 316 ms 26320 KB Output is correct
5 Correct 343 ms 25920 KB Output is correct
6 Correct 249 ms 25920 KB Output is correct
7 Correct 326 ms 23184 KB Output is correct
8 Correct 206 ms 32444 KB Output is correct
9 Correct 96 ms 20484 KB Output is correct