oj.uz

Submission #255594

# Submission time Handle Problem Language Result Execution time Memory
255594 2020-08-01T11:57:10 Z shayan_p Ball Machine (BOI13_ballmachine) C++14
100 / 100
 303 ms 28464 KB 
// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

bool FRE[maxn];
set<int> fre;
int mn[maxn];
vector<int> v[maxn];
int st[maxn], rst[maxn];
int sp[20][maxn];

void prep(int u){
    for(int i = 1; i < 20; i++)
	sp[i][u] = sp[i-1][sp[i-1][u]];
    mn[u] = u;
    for(int y : v[u]){
	sp[0][y] = u;
	prep(y);
	mn[u] = min(mn[u], mn[y]);
    }
    sort(v[u].begin(), v[u].end(), [&](int i, int j){ return mn[i] < mn[j]; });
}
void prep2(int u){
    static int C = 0;
    for(int y : v[u]){
	prep2(y);
    }
    st[u] = C;
    rst[C] = u;
    C++;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n, q;
    cin >> n >> q;
    int root = -1;
    for(int i = 1; i <= n; i++){
	int p;
	cin >> p;
	if(p == 0)
	    root = i;
	else
	    v[p].PB(i);
    }
    
    st[0] = n;
    FRE[n] = 1;
    
    prep(root);
    prep2(root);
    for(int i = 0; i < n; i++){
	fre.insert(fre.end(), i);
	FRE[i] = 1;
    }
    while(q--){
	int task;
	cin >> task;
	int ans = 0;
	if(task == 1){
	    int k;
	    cin >> k;
	    while(k--){
		int id = *fre.begin();
		FRE[id] = 0;
		fre.erase(id);
		ans = rst[id];
	    }
	}
	else{
	    int u;
	    cin >> u;
	    for(int i = 19; i >= 0; i--){
		if(FRE[ st[ sp[i][u] ] ] == 0)
		    u = sp[i][u], ans+= 1<<i;
	    }
	    u = st[u];
	    fre.insert(u);
	    FRE[u] = 1;
	}
	cout << ans << "\n";
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 153 ms 13304 KB Output is correct
3 Correct 90 ms 13432 KB Output is correct
4 Correct 2 ms 2816 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct
6 Correct 3 ms 2944 KB Output is correct
7 Correct 3 ms 2944 KB Output is correct
8 Correct 3 ms 2944 KB Output is correct
9 Correct 9 ms 3456 KB Output is correct
10 Correct 29 ms 5504 KB Output is correct
11 Correct 282 ms 13304 KB Output is correct
12 Correct 86 ms 13560 KB Output is correct
13 Correct 120 ms 13432 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 7800 KB Output is correct
2 Correct 211 ms 22904 KB Output is correct
3 Correct 97 ms 18292 KB Output is correct
4 Correct 75 ms 9188 KB Output is correct
5 Correct 85 ms 8952 KB Output is correct
6 Correct 64 ms 9080 KB Output is correct
7 Correct 79 ms 8056 KB Output is correct
8 Correct 36 ms 7800 KB Output is correct
9 Correct 188 ms 23412 KB Output is correct
10 Correct 234 ms 22904 KB Output is correct
11 Correct 172 ms 22904 KB Output is correct
12 Correct 182 ms 20728 KB Output is correct
13 Correct 120 ms 25256 KB Output is correct
14 Correct 101 ms 18176 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 13144 KB Output is correct
2 Correct 236 ms 21220 KB Output is correct
3 Correct 155 ms 23160 KB Output is correct
4 Correct 138 ms 19320 KB Output is correct
5 Correct 148 ms 18936 KB Output is correct
6 Correct 162 ms 18936 KB Output is correct
7 Correct 152 ms 17268 KB Output is correct
8 Correct 178 ms 23084 KB Output is correct
9 Correct 255 ms 23576 KB Output is correct
10 Correct 235 ms 23160 KB Output is correct
11 Correct 230 ms 23160 KB Output is correct
12 Correct 232 ms 21368 KB Output is correct
13 Correct 267 ms 28464 KB Output is correct
14 Correct 179 ms 18548 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 23672 KB Output is correct
2 Correct 286 ms 21228 KB Output is correct
3 Correct 151 ms 28152 KB Output is correct
4 Correct 297 ms 23800 KB Output is correct
5 Correct 286 ms 23160 KB Output is correct
6 Correct 232 ms 23160 KB Output is correct
7 Correct 303 ms 21228 KB Output is correct
8 Correct 142 ms 28152 KB Output is correct
9 Correct 92 ms 18292 KB Output is correct