Submission #1162267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162267		Almonther	September (APIO24_september)	C++17	100 / 100	118 ms	15552 KiB

september

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define co cout<<
// stuff
const int maxn=1e5+5;
vector<ll>v[maxn];
ll par[maxn],vis[maxn];
void dfs(ll x){
    for(auto i:v[x]){
        if(i==par[x]) continue;
        par[i]=x;
        dfs(i);
    }
}
int solve(int N,int M,vector<int>F,vector<vector<int>>S){
    ll cnt=0,ans=0,apear[N]={};
    set<ll>s;
    for(int i=1;i<N;i++) v[F[i]].push_back(i);
    dfs(0);
    for(int j=0;j<N-1;j++){
        for(int i=0;i<M;i++){
            apear[S[i][j]]++;
            if(apear[S[i][j]]==1) cnt++;
            if(apear[S[i][j]]==M) cnt--;
            if(i==0){
                s.erase(S[i][j]);
                for(auto k:v[S[i][j]]){
                    if(k==par[S[i][j]]) continue;
                    if(vis[k]==0) s.insert(k);
                }
                vis[S[i][j]]=1;
            }
        }
        if(cnt==0&&s.size()==0) ans++;
    }
    for(int i=0;i<N;i++){
        v[i].clear();
        vis[i]=0;
        par[i]=0;
    }
    s.clear();
    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