Submission #1192376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192376		kangsan	September (APIO24_september)	C++20	100 / 100	139 ms	17600 KiB

september

#include "september.h"
#include<bits/stdc++.h>
using namespace std;

const int LM=100100;
int pw[LM], pk[LM], pks[LM], n;
int ch[LM];
vector<int> child[LM];
int ldfs;

void C(int N, int M, vector<int>F, vector<vector<int>> S){
    for(int i=0; i<=N; i++){
        child[i].clear();
        pw[i]=0;
        ch[i]=0;
    }
    for(int i=1; i<N; i++)
        child[F[i]].push_back(i);
    n=N;
    ldfs=1;
}

void dfs(int x){
    int s=ldfs;
    for(int y:child[x])
        dfs(y);
    pks[ldfs]=s;
    pk[x] = ldfs++;
}

void updt_pw(int x){
    for(int i=x; i<=n; i+=(i&-i))
        pw[i]++;
}

int find_pw(int x){
    int ret=0;
    for(int i=x; i>0; i-=(i&-i))
        ret += pw[i];
    
    for(int i=pks[x]-1; i>0; i-=(i&-i))
        ret -= pw[i];
    return ret==x-pks[x]+1;
}


int solve(int N, int M, vector<int>F, vector<vector<int>> S){
    C(N, M, F, S);
    dfs(0);
    int ans=0;
    
    queue<int> q;
    int h=0;
    
    for(int i=0; i<n-1; i++){
        for(int j=0; j<M; j++){
            int s=S[j][i];
            ch[s]++;
            h += ch[s]==M;
            if(ch[s]>1) continue;
            
            updt_pw(pk[s]);
            if(!find_pw(pk[s]))
                q.push(pk[s]);
        }
        if(h==i+1){
            while(!q.empty() && find_pw(q.front()))
                q.pop();
            ans += q.empty();
        }
    }
    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