Submission #1062575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062575		alexdd	September (APIO24_september)	C++17	100 / 100	133 ms	24784 KiB

september

#include "september.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
vector<int> con[100005];
int mint[100005],maxt[100005];
int submin[100005],submax[100005];
int mars[100005];
void same_day(int le, int ri)
{
    if(le>=ri)
        return;
    //cout<<le<<" "<<ri<<"  same day\n";
    mars[le+1]++;
    mars[ri+1]--;
}
void dfs(int nod)
{
    submin[nod]=mint[nod];
    submax[nod]=maxt[nod];
    for(auto adj:con[nod])
    {
        dfs(adj);
        submin[nod] = min(submin[nod], submin[adj]);
        submax[nod] = max(submax[nod], submax[adj]);
    }
    //cout<<nod<<"  "<<mint[nod]<<" "<<submax[nod]<<" zzz\n";
    if(nod>0) same_day(mint[nod],submax[nod]);
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S)
{
    for(int i=0;i<N;i++)
    {
        con[i].clear();
        mint[i]=INF;
        maxt[i]=-1;
        mars[i]=0;
    }
    for(int i=1;i<N;i++)
    {
        con[F[i]].push_back(i);
    }
    for(int i=0;i<M;i++)
    {
        for(int j=0;j<N-1;j++)
        {
            mint[S[i][j]] = min(mint[S[i][j]], j);
            maxt[S[i][j]] = max(maxt[S[i][j]], j);
        }
    }
    dfs(0);
    int cnt=1;
    for(int i=1;i<N-1;i++)
    {
        mars[i] += mars[i-1];
        if(mars[i]==0)
        {
            cnt++;
        }
    }
    return cnt;
}

• 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