Submission #255594

#	Time	Username	Problem	Language	Result	Execution time	Memory
255594		shayan_p	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	303 ms	28464 KiB

ballmachine

// 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 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5