Submission #1200105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200105		prince	September (APIO24_september)	C++17	In queue	0 ms	0 KiB

september

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

vector<vector<int>>g;
vector<bool>vis;
set<int>st;

void dfs(int u){
    vis[u]=true;
    for(int v:g[u]){
        if(!vis[v])st.insert(v),dfs(v);
    }
}

int solve(int n,int m,vector<int>a,vector<vector<int>>vol){
    g.assign(n,{});
    for(int i=0;i<n;i++){
        if(a[i]>=0)g[a[i]].push_back(i);
    }
    int mn = 1e9;
    for(int j=0;j<m;j++){
        st.clear();
        vis.assign(n,false);
        int cnt=0;
        for(int i=0;i+1<n;i++){
            int x = vol[j][i];
            if(st.count(x))st.erase(x);
            else dfs(x);
            if(st.empty())cnt++;
        }
        mn=min(mn,cnt);
    }
    return mn;
}