Submission #1201230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201230		meligy122	September (APIO24_september)	C++20	100 / 100	126 ms	13760 KiB

september

#include<bits/stdc++.h>
#include "september.h"

using namespace std;

#define ll long long
#define Meligy ios_base::sync_with_stdio(false); cin.tie(NULL);

const int Nx=2e5 + 5;
vector<ll>adj[Nx];
bool vis[Nx];
set<int>st;
void bfs(int s){
    queue<int>q;
    vis[s]=1;
    q.push(s);
    while(!q.empty()) {
        int cur=q.front();
        q.pop();
        for(auto &v:adj[cur]){
            if(vis[v])continue;
            st.insert(v);
            vis[v]=1;
            q.push(v);
        }
    }
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S){
    for(int i=1;i<N;i++){
        adj[F[i]].push_back(i);
    }
    int ans=0;
    ll c[N+1];
    memset(c,0,sizeof(c));
    int l=0;
    for(int i=0;i<N-1;i++){
        for(int m=0;m<M;m++){
            c[S[m][i]]++;
        }
        bool f=1;
        for(int j=l;j<=i;j++){
            for(int m=0;m<M;m++){
                if(c[S[m][j]]<M)f=0;
            }
            if(f==0)break;
        }
        if(f==0)continue;
        for(int j=l;j<=i;j++){
            if(!vis[S[0][j]]){
                bfs(S[0][j]);
            }
            else{
                st.erase(st.find(S[0][j]));
            }
        }
        if(st.empty())ans++;
        l=i+1;
    }
    for(int i=0;i<N;i++) {
        adj[i].clear();
        vis[i]=0;
    }
    st.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