Submission #1016062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016062		amine_aroua	September (APIO24_september)	C++17	100 / 100	157 ms	15312 KiB

september

#include "september.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<bool> vis;
int Time = -1;
void dfs(int x)
{
    if(vis[x])
        return ;
    vis[x] = 1;
    Time++;
    for(auto u : adj[x])
    {
        dfs(u);
    }
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S)
{
    adj.clear();
    adj.assign(N , {});
    vis.assign(N , 0);
    Time = -1;
    for(int i = 1 ; i <= N - 1 ; i++)
    {
        adj[F[i]].push_back(i);
    }
    int d = 0;
    vector<int> occ(N);
    set<int> diff;
    for(int i = 0 ; i < N - 1 ; i++)
    {
        for(int j = 0 ; j < M ; j++)
        {
            dfs(S[j][i]);
            if(occ[S[j][i]] == 0)
                diff.insert(S[j][i]);
            if(occ[S[j][i]] + 1 == M)
            {
                diff.erase(S[j][i]);
            }
            occ[S[j][i]]++;
        }
        if(diff.empty() && Time == 0)
        {
            d++;
        }
        Time--;
    }
    return d;
}

• 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