Submission #993059

#	Time	Username	Problem	Language	Result	Execution time	Memory
993059		boris_mihov	September (APIO24_september)	C++17	100 / 100	172 ms	15692 KiB

september

#include "september.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;

int n, m;
struct Fenwick
{   
    int tree[MAXN];
    void reset()
    {
        std::fill(tree, tree + n + 1, 0);
    }

    void update(int idx, int val)
    {
        for (; idx <= n ; idx += idx & (-idx))
        {
            tree[idx] += val;
        }
    }

    int query(int idx)
    {
        int res = 0;
        for (; idx ; idx -= idx & (-idx))
        {
            res += tree[idx];
        }

        return res;
    }

    void rangeUpdate(int l, int r)
    {
        update(l, 1);
        update(r + 1, -1);
    }

    int query(int l, int r)
    {
        return query(r) - query(l - 1);
    }
};

bool added[MAXN];
Fenwick childTree;
Fenwick parentTree;
std::vector <int> g[MAXN];
int count[MAXN];
int count2[MAXN];
int in[MAXN];
int out[MAXN];
int timer;

void dfs(int node)
{
    in[node] = ++timer;
    for (const int &u : g[node])
    {
        dfs(u);
    }

    out[node] = timer;
}

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S)
{
    n = N;
    m = M;
    for (int i = 1 ; i <= n ; ++i)
    {
        g[i].clear();
        added[i] = 0;
        count[i] = count2[i] = 0;
    }

    for (int i = 1 ; i < n ; ++i)
    {
        g[F[i] + 1].push_back(i + 1);
    }

    childTree.reset();
    parentTree.reset();
    timer = 0;
    dfs(1);

	for (int i = 1 ; i <= n ; ++i)
    {
        childTree.update(i, 1);
    }

    int badCnt = 0;    
    int answer = 0;
    for (int i = 0 ; i < n - 1 ; ++i)
    {
        for (int person = 0 ; person < m ; ++person)
        {
            S[person][i]++;
            int node = S[person][i];
            count2[count[node]]--;
            count[node]++;
            count2[count[node]]++;

            if (!added[node])
            {
                badCnt += childTree.query(in[node], out[node]);
                childTree.update(in[node], -1);
                parentTree.rangeUpdate(in[node], out[node]);
                badCnt -= parentTree.query(in[node]);
                added[node] = true;
            }
        }

        if (badCnt == 0 && count2[m] == i + 1)
        {
            answer++;
        }
    }

    return answer;
}

• 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