제출 #1157429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157429		rayan_bd	September (APIO24_september)	C++20	45 / 100	119 ms	20680 KiB

september

#include <bits/stdc++.h>

using namespace std;


const int mxB = 17;
const int mxN = 1e5+10;
vector<int> adj[mxN];
int st[mxN],en[mxN],nxt[mxN],idx[mxN],lt[mxN],dp[mxB][mxN],rmax[mxN],timer=-1;

// next[u] -> index of the rightmost node that belongs to the u nodes subtree

void dfs(int u=0,int par=-1){
	st[u]=++timer;
	lt[timer]=idx[u];
	for(auto it:adj[u]){
		if(it^par){
			dfs(it,u);
		}
	}
	en[u]=timer;
}

void build_sparse(int N){
	for(int i=0;i<N;++i){
		dp[0][i]=lt[i];
	}
	for(int i=1;i<mxB;++i){
    	for(int j=0;j+(1<<i)<=N;++j){
    		dp[i][j]=max(dp[i-1][j],dp[i-1][j+(1<<(i-1))]);
    	}
    }
}

int qry(int l,int r){
	int cnt = r-l+1;
	int k=(int)(log(cnt)/log(2));
	return max(dp[k][l],dp[k][r-(1<<k)+1]);
}

void reset(int N){
	timer=-1;
	for(int i=0;i<=N;++i) adj[i].clear();
}

int solve(int N,int M,vector<int> F,vector<vector<int>> S){
	reset(N);

	for(int i=1;i<N;++i) adj[F[i]].push_back(i);
	for(int i=1;i<=S[0].size();++i) idx[S[0][i-1]]=i;

	dfs();
	build_sparse(N);

	for(int i=0;i<N;++i) nxt[i]=qry(st[i],en[i]);

	for(int i=1;i<=S[0].size();++i) rmax[i]=max(rmax[i-1],nxt[S[0][i-1]]);

	int idx=1,ans=0;

	while(idx<=S[0].size()){
		if(rmax[idx]==idx) ++ans,++idx;
		else idx=rmax[idx];
	}

	return ans;
}

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