Submission #1116248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116248		boris_7	September (APIO24_september)	C++17	100 / 100	437 ms	26036 KiB

september

#include "september.h"

#include <vector>
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

vector<vector<int>>gp;
vector<int>ent,seg,v;

void update(int l,int r,int u,int x){
	if(l==r && l==x){
		seg[u]=1;
		return;
	}
	int mid = (l+r)/2;
	if(mid>=x) update(l,mid,u*2+1,x);
	else update(mid+1,r,u*2+2,x);
	seg[u]=seg[u*2+1]+seg[u*2+2];
}

int get(int l,int r,int u,int lx,int rx){
	if(l>=lx && r<=rx) return seg[u];
	if(l>rx || r<lx) return 0;
	int mid = (l+r)/2;
	return get(l,mid,u*2+1,lx,rx)+get(mid+1,r,u*2+2,lx,rx);
}

void dfs(int u,int p){
	v.push_back(u);
	for(int &i:gp[u]){
		if(i!=p){
			dfs(i,u);
			ent[u]+=ent[i];
		}
	}
}

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
	gp = vector<vector<int>>(N);
	vector<int>sub(N,1);
	v.clear();
	for(int i = 1;i<N;i++){
		gp[F[i]].push_back(i);
		gp[i].push_back(F[i]);
	}
	int ans = 0;
	ent = vector<int>(N,1);
	dfs(0,-1);
	vector<int>place(N),t(N),ok(N);
	for(int i = 0;i<N;i++) place[v[i]]=i;
	int s = 1;
	set<int>st;
	while(s<N) s*=2;
	seg = vector<int>(2*s);
	for(int k = 0;k+1<N;k++){
		for(int i = 0;i<M;i++){
			int u = S[i][k];
			st.insert(u);
			t[u]++;
			update(0,s-1,0,place[u]);
		}
		while(st.size()){
			int u = *st.rbegin();
			if(t[u]!=M) break;
			if(get(0,s-1,0,place[u],place[u]+ent[u]-1)==ent[u]){
				st.erase(u);
			}
			else break;
		}
		if(st.empty()){
			ans++;
		}
	}
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 11 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 9 / 9
• Subtask 10: 16 / 16