oj.uz

Submission #138022

# Submission time Handle Problem Language Result Execution time Memory
138022 2019-07-29T00:32:26 Z silxikys Ball Machine (BOI13_ballmachine) C++14
7.53968 / 100
 169 ms 28324 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 2808 KB Output isn't correct
2 Incorrect 102 ms 15348 KB Output isn't correct
3 Incorrect 80 ms 15608 KB Output isn't correct
4 Incorrect 4 ms 2808 KB Output isn't correct
5 Incorrect 5 ms 2808 KB Output isn't correct
6 Incorrect 5 ms 2936 KB Output isn't correct
7 Incorrect 5 ms 2936 KB Output isn't correct
8 Incorrect 5 ms 2936 KB Output isn't correct
9 Incorrect 9 ms 3676 KB Output isn't correct
10 Incorrect 22 ms 6008 KB Output isn't correct
11 Incorrect 107 ms 15468 KB Output isn't correct
12 Incorrect 80 ms 15656 KB Output isn't correct
13 Incorrect 87 ms 15352 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 7800 KB Output is correct
2 Incorrect 126 ms 24696 KB Output isn't correct
3 Incorrect 89 ms 21748 KB Output isn't correct
4 Incorrect 59 ms 9720 KB Output isn't correct
5 Incorrect 59 ms 9592 KB Output isn't correct
6 Incorrect 54 ms 9464 KB Output isn't correct
7 Incorrect 55 ms 8824 KB Output isn't correct
8 Correct 43 ms 7724 KB Output is correct
9 Incorrect 127 ms 25124 KB Output isn't correct
10 Incorrect 119 ms 24568 KB Output isn't correct
11 Incorrect 107 ms 24532 KB Output isn't correct
12 Incorrect 121 ms 23032 KB Output isn't correct
13 Correct 103 ms 25336 KB Output is correct
14 Incorrect 92 ms 21748 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 14072 KB Output isn't correct
2 Incorrect 149 ms 23344 KB Output isn't correct
3 Incorrect 98 ms 23032 KB Output isn't correct
4 Incorrect 91 ms 20772 KB Output isn't correct
5 Incorrect 95 ms 20316 KB Output isn't correct
6 Incorrect 92 ms 20344 KB Output isn't correct
7 Incorrect 90 ms 19360 KB Output isn't correct
8 Incorrect 93 ms 23208 KB Output isn't correct
9 Incorrect 165 ms 24948 KB Output isn't correct
10 Incorrect 146 ms 24612 KB Output isn't correct
11 Incorrect 138 ms 24668 KB Output isn't correct
12 Incorrect 142 ms 23416 KB Output isn't correct
13 Incorrect 144 ms 28072 KB Output isn't correct
14 Incorrect 142 ms 21608 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 134 ms 25012 KB Output isn't correct
2 Incorrect 138 ms 23288 KB Output isn't correct
3 Correct 120 ms 28324 KB Output is correct
4 Incorrect 128 ms 25100 KB Output isn't correct
5 Incorrect 136 ms 24540 KB Output isn't correct
6 Incorrect 137 ms 24540 KB Output isn't correct
7 Incorrect 169 ms 23416 KB Output isn't correct
8 Correct 121 ms 28280 KB Output is correct
9 Incorrect 90 ms 21748 KB Output isn't correct