Submission #1015978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015978		amine_aroua	September (APIO24_september)	C++17	0 / 100	1 ms	348 KiB

september

#include "september.h"

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
int Time = -1;
vector<int> tin , tout;
void dfs(int x)
{
    tin[x] = ++Time;
    for(auto u : adj[x])
    {
        dfs(u);
    }
    tout[x] = Time;
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S)
{
    adj.clear();
    adj.assign(N , {});
    tin.clear();
    tout.clear();
    tin.assign(N , 0);
    Time = -1;
    tout = tin;
    for(int i = 1 ; i <= N - 1 ; i++)
    {
        adj[F[i]].push_back(i);
    }
    dfs(0);
    int d = 0;
    vector<pair<int ,int>> cur(M , {1e9 , -1e9});
    for(int i = 0 ; i < N - 1 ; i++)
    {
        set<pair<int,int>> s;
        int a = 0 , b = 0;
        for(int j = 0 ; j < M ; j++)
        {
            cur[j].first = min(cur[j].first , tin[S[j][i]]);
            a = cur[j].first;
            cur[j].second = max(cur[j].second , tin[S[j][i]]);
            b = cur[j].second;
            s.insert({cur[j].first , cur[j].second});
        }
        if((int)s.size() == 1 && (b - a + 1 == i + 1))
        {
            d++;
        }
    }
	return d;
}

• 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