oj.uz

Submission #138021

# Submission time Handle Problem Language Result Execution time Memory
138021 2019-07-29T00:14:15 Z silxikys Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 838 ms 29756 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]) {
        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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2936 KB Output isn't correct
2 Incorrect 212 ms 16396 KB Output isn't correct
3 Incorrect 107 ms 16404 KB Output isn't correct
4 Incorrect 4 ms 2808 KB Output isn't correct
5 Incorrect 4 ms 2808 KB Output isn't correct
6 Incorrect 5 ms 2936 KB Output isn't correct
7 Incorrect 5 ms 3064 KB Output isn't correct
8 Incorrect 6 ms 3064 KB Output isn't correct
9 Incorrect 14 ms 3636 KB Output isn't correct
10 Incorrect 37 ms 6136 KB Output isn't correct
11 Incorrect 225 ms 16456 KB Output isn't correct
12 Incorrect 115 ms 16376 KB Output isn't correct
13 Incorrect 186 ms 16476 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 8184 KB Output is correct
2 Incorrect 671 ms 26160 KB Output isn't correct
3 Incorrect 117 ms 22644 KB Output isn't correct
4 Incorrect 179 ms 10332 KB Output isn't correct
5 Incorrect 309 ms 10196 KB Output isn't correct
6 Incorrect 293 ms 10268 KB Output isn't correct
7 Incorrect 288 ms 9336 KB Output isn't correct
8 Correct 81 ms 8184 KB Output is correct
9 Incorrect 436 ms 26224 KB Output isn't correct
10 Incorrect 547 ms 25976 KB Output isn't correct
11 Incorrect 388 ms 25864 KB Output isn't correct
12 Incorrect 493 ms 24312 KB Output isn't correct
13 Correct 159 ms 26452 KB Output is correct
14 Incorrect 100 ms 22644 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 169 ms 14584 KB Output isn't correct
2 Incorrect 663 ms 24804 KB Output isn't correct
3 Correct 440 ms 24044 KB Output is correct
4 Incorrect 261 ms 21472 KB Output isn't correct
5 Incorrect 383 ms 21180 KB Output isn't correct
6 Incorrect 367 ms 21368 KB Output isn't correct
7 Incorrect 351 ms 20216 KB Output isn't correct
8 Correct 349 ms 24032 KB Output is correct
9 Incorrect 408 ms 26348 KB Output isn't correct
10 Incorrect 838 ms 25996 KB Output isn't correct
11 Incorrect 619 ms 25976 KB Output isn't correct
12 Incorrect 613 ms 24880 KB Output isn't correct
13 Correct 567 ms 29756 KB Output is correct
14 Incorrect 203 ms 22936 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 497 ms 26464 KB Output isn't correct
2 Incorrect 621 ms 24924 KB Output isn't correct
3 Correct 189 ms 29292 KB Output is correct
4 Incorrect 525 ms 26488 KB Output isn't correct
5 Incorrect 636 ms 26104 KB Output isn't correct
6 Incorrect 456 ms 26008 KB Output isn't correct
7 Incorrect 580 ms 24696 KB Output isn't correct
8 Correct 173 ms 29304 KB Output is correct
9 Incorrect 118 ms 22704 KB Output isn't correct