Submission #1194967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194967		Aestivate	September (APIO24_september)	C++20	0 / 100	1095 ms	320 KiB

september

#include<bits/stdc++.h>
using namespace std;
#define pb push_back


int solve(int n, int m, vector<int>f, vector<vector<int>>s){
    int tot=0;
    vector<int>ne(n+1, 0);
    vector<vector<int>>node(n, vector<int>());
    // cerr<<node.size()<<"\n";
    // cerr<<n<<" "<<node.size()<<" "<<ne.size()<<"\n";

	auto go = [&](auto self, int u) -> void
	{
        if(ne[u]) return;
        tot++;
        ne[u]=1;
        
		for(auto i: node[u])
			self(self, i);
	};
    for(int i=1;i<n;i++){
        node[f[i]].pb(i);
    }
    int now=0;
    int ans=0;
    vector<int>vis(n+1, 0);
    while(now<n-1){
        for(int i=0;i<s.size();i++){
            if(vis[s[i][now]]) continue;
            go(go, s[i][now]);
            tot--;
            vis[s[i][now]]=1;
        }
        now++;
        bool ok=0;
        while(!ok||tot){
            if(now==n-1) break;
            bool ok2=1;
            for(int i=0;i<s.size();i++){
                if(vis[s[i][now]]){
                    ok2=0;
                    break;
                }
            }
            if(!ok2){
                for(int i=0;i<s.size();i++){
                    if(vis[s[i][now]]) continue;
                    go(go, s[i][now]);
                    tot--;
                    vis[s[i][now]]=1;
                }
                now++;
                ok=0;
            }
            else ok=1;
        }
        ans++;
    }
    return ans;
}

// int main(){
//     int t;
//     cin>>t;
//     while(t--)
//         cout<<solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4,  1, 2, 3}})<<" "<<solve(3, 1, {-1, 0, 0}, {{1, 2}})<<"\n";
// }

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