oj.uz

답안 #58966

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58966 2018-07-19T21:51:36 Z Benq Ball Machine (BOI13_ballmachine) C++11
100 / 100
 342 ms 54244 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int N,Q, root, mn[MX], par[MX][17], key[MX], rkey[MX], p[MX], oc[MX];
vi child[MX];
set<int> lef;

void dfs(int a) {
    mn[a] = a;
    for (int i: child[a]) {
        dfs(i);
        mn[a] = min(mn[a],mn[i]);
    }
    sort(all(child[a]),[](int x, int y) { return mn[x] < mn[y]; });
}

int nex = 0;

int dfs2(int a) {
    vi v;
    for (int i: child[a]) v.pb(dfs2(i));
    key[++nex] = a;
    rkey[a] = nex;
    for (int i: v) par[i][0] = nex;
    // cout << nex << " " << a << "\n";
    return nex;
}

void genTree() {
    dfs(root);
    dfs2(root);
    FOR(j,1,17) FOR(i,1,N+1) par[i][j] = par[par[i][j-1]][j-1]; 
}

int ad() {
    int x = *lef.begin();
    oc[x] = 1;
    lef.erase(x);
    return key[x];
}

int rem(int x) {
    int cur = rkey[x], ans = 0;
    F0Rd(i,17) if (oc[par[cur][i]]) {
        cur = par[cur][i];
        ans ^= 1<<i;
    }
    // cout << "AH " << x << " " << cur << "\n";
    oc[cur] = 0; lef.insert(cur);
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> Q;
    FOR(i,1,N+1) {
        cin >> p[i];
        if (p[i] == 0) root = i;
        else child[p[i]].pb(i);
    }
    genTree();
    FOR(i,1,N+1) lef.insert(i);
    F0R(i,Q) {
        int t,x; cin >> t >> x;
        if (t == 1) {
            int ans = 0;
            F0R(i,x) ans = ad();
            cout << ans << "\n";
        } else {
            cout << rem(x) << "\n";
        }
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 193 ms 13800 KB Output is correct
3 Correct 98 ms 14904 KB Output is correct
4 Correct 5 ms 14904 KB Output is correct
5 Correct 6 ms 14904 KB Output is correct
6 Correct 6 ms 14904 KB Output is correct
7 Correct 7 ms 14904 KB Output is correct
8 Correct 9 ms 14904 KB Output is correct
9 Correct 13 ms 14904 KB Output is correct
10 Correct 40 ms 14904 KB Output is correct
11 Correct 277 ms 16616 KB Output is correct
12 Correct 164 ms 17372 KB Output is correct
13 Correct 176 ms 18328 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 18328 KB Output is correct
2 Correct 238 ms 30564 KB Output is correct
3 Correct 121 ms 30564 KB Output is correct
4 Correct 100 ms 30564 KB Output is correct
5 Correct 107 ms 30564 KB Output is correct
6 Correct 86 ms 30564 KB Output is correct
7 Correct 97 ms 30564 KB Output is correct
8 Correct 50 ms 30564 KB Output is correct
9 Correct 188 ms 36872 KB Output is correct
10 Correct 264 ms 37820 KB Output is correct
11 Correct 229 ms 39004 KB Output is correct
12 Correct 242 ms 39004 KB Output is correct
13 Correct 233 ms 44488 KB Output is correct
14 Correct 118 ms 44488 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 44488 KB Output is correct
2 Correct 249 ms 44488 KB Output is correct
3 Correct 216 ms 46432 KB Output is correct
4 Correct 199 ms 46432 KB Output is correct
5 Correct 211 ms 46432 KB Output is correct
6 Correct 195 ms 46432 KB Output is correct
7 Correct 192 ms 46432 KB Output is correct
8 Correct 188 ms 48608 KB Output is correct
9 Correct 291 ms 48608 KB Output is correct
10 Correct 342 ms 48608 KB Output is correct
11 Correct 326 ms 48608 KB Output is correct
12 Correct 302 ms 48608 KB Output is correct
13 Correct 338 ms 54244 KB Output is correct
14 Correct 295 ms 54244 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 265 ms 54244 KB Output is correct
2 Correct 289 ms 54244 KB Output is correct
3 Correct 257 ms 54244 KB Output is correct
4 Correct 266 ms 54244 KB Output is correct
5 Correct 271 ms 54244 KB Output is correct
6 Correct 244 ms 54244 KB Output is correct
7 Correct 286 ms 54244 KB Output is correct
8 Correct 160 ms 54244 KB Output is correct
9 Correct 127 ms 54244 KB Output is correct