oj.uz

Submission #138026

# Submission time Handle Problem Language Result Execution time Memory
138026 2019-07-29T01:25:25 Z silxikys Ball Machine (BOI13_ballmachine) C++14
100 / 100
 706 ms 30444 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e5+5;
const int INV = -1;
int N, Q;
vector<int> adj[maxn];

struct Node {
	int s, e, m;
	//covers s,e;
	int sum;
	int lazy;
	Node *l, *r;
	
	Node(int a, int b) {
		s = a;
		e = b;
		sum = 0;
		lazy = INV;
		if (s != e) {
			m = (s+e)/2;
			l = new Node(s,m);
			r = new Node(m+1,e);
            sum = l->sum + r->sum;
		}
		else {
			l = NULL;
			r = NULL;
            sum = 1;
		}
	}

	void push() {
		if (lazy == INV) return;
		if (s != e) {
			l->lazy = lazy;
			l->sum = (l->e - l->s + 1) * lazy;

			r->lazy = lazy;
			r->sum = (r->e - r->s + 1) * lazy;
		}
		lazy = INV;
	}

	void pull() {
		sum = l->sum + r->sum;
	}

	void add(int st, int en, int x) {
		//lazy: already accounted for in your own node, not the childs nodes
		if (st <= s && e <= en) {
			lazy = x;
			sum = (e - s + 1) * x;
			return;
		}
		push();
		if (st <= m) {
			l->add(st,en,x);
		}
		if (en > m) {
			r->add(st,en,x);
		}
		pull();
	}

    int find(int k) {
        push();
        //cout << s << ' ' << e << '\n';
        if (s == e) return s;
        if (l->sum >= k) {
            return l->find(k);
        }
        return r->find(k-l->sum);
    }

	int getsum(int st, int en) {
		push();
		//if completely included
		if (st <= s && e <= en) {
			return sum;
		}
		int ret = 0;
		if (st <= m) {
			ret += l->getsum(st,en);
		}
		if (en > m) {
			ret += r->getsum(st,en);
		}
		return ret;
	}
};

int minsub[maxn];
int ord[maxn], inv[maxn]; //node to seg, seg to node
int pt = 1;

void prep(int i) {
    minsub[i] = i;
    for (int j: adj[i]) {
        prep(j);
        minsub[i] = min(minsub[i],minsub[j]);
    }
    sort(adj[i].begin(),adj[i].end(),[](int a, int b) {
            return minsub[a] < minsub[b];
            });
}
void dfs(int i) {
    for (int j: adj[i]) {
        dfs(j);
    }
    ord[i] = pt;
    inv[pt] = i;
    pt++;
    //cout << i << ' ';
}

const int maxk = 18;
int par[maxk][maxn];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> Q;
    int rt = -1;
    for (int i = 1; i <= N; i++) {
        int pi; cin >> pi;
        if (pi == 0) rt = i;
        else adj[pi].push_back(i);
        par[0][i] = pi;
    }
    for (int k = 1; k < maxk; k++) {
        for (int i = 1; i <= N; i++) {
            par[k][i] = par[k-1][par[k-1][i]];
        }
    }
    prep(rt);
    dfs(rt);
    Node *root = new Node(1,N);
    while (Q--) {
        int t; cin >> t;
        if (t == 1) {
            int k; cin >> k;
            int r = root->find(k);
            root->add(1,r,0);
            cout << inv[r] << '\n';
        }
        else {
            int v; cin >> v;
            int res = 0;
            for (int k = maxk - 1; k >= 0; k--) {
                if (par[k][v] == 0) continue;
                int nxt = par[k][v];
                if (root->getsum(ord[nxt],ord[nxt]) == 0) {
                    res += (1<<k);
                    v = nxt;
                }
            }
            root->add(ord[v],ord[v],1); //set it to empty
            cout << res << '\n';
        }
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 203 ms 15608 KB Output is correct
3 Correct 91 ms 15928 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2780 KB Output is correct
6 Correct 5 ms 2936 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 6 ms 2936 KB Output is correct
9 Correct 14 ms 3708 KB Output is correct
10 Correct 36 ms 5964 KB Output is correct
11 Correct 212 ms 15480 KB Output is correct
12 Correct 88 ms 15736 KB Output is correct
13 Correct 159 ms 15480 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8012 KB Output is correct
2 Correct 600 ms 25624 KB Output is correct
3 Correct 102 ms 21876 KB Output is correct
4 Correct 165 ms 9848 KB Output is correct
5 Correct 263 ms 9720 KB Output is correct
6 Correct 255 ms 9720 KB Output is correct
7 Correct 274 ms 8764 KB Output is correct
8 Correct 75 ms 7928 KB Output is correct
9 Correct 445 ms 26044 KB Output is correct
10 Correct 643 ms 25592 KB Output is correct
11 Correct 427 ms 25720 KB Output is correct
12 Correct 514 ms 23612 KB Output is correct
13 Correct 173 ms 27128 KB Output is correct
14 Correct 102 ms 21872 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 14456 KB Output is correct
2 Correct 634 ms 24348 KB Output is correct
3 Correct 341 ms 24860 KB Output is correct
4 Correct 263 ms 21496 KB Output is correct
5 Correct 386 ms 21104 KB Output is correct
6 Correct 391 ms 21240 KB Output is correct
7 Correct 346 ms 19832 KB Output is correct
8 Correct 351 ms 24700 KB Output is correct
9 Correct 426 ms 26240 KB Output is correct
10 Correct 651 ms 25976 KB Output is correct
11 Correct 655 ms 25744 KB Output is correct
12 Correct 610 ms 24148 KB Output is correct
13 Correct 625 ms 30444 KB Output is correct
14 Correct 207 ms 21960 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 26300 KB Output is correct
2 Correct 623 ms 24332 KB Output is correct
3 Correct 203 ms 30192 KB Output is correct
4 Correct 472 ms 26276 KB Output is correct
5 Correct 706 ms 25840 KB Output is correct
6 Correct 452 ms 25996 KB Output is correct
7 Correct 620 ms 24184 KB Output is correct
8 Correct 201 ms 30148 KB Output is correct
9 Correct 99 ms 21872 KB Output is correct