Submission #1015999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015999		amine_aroua	September (APIO24_september)	C++17	0 / 100	1 ms	604 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;
}
struct DSU
{
    vector<int> e;
    vector<pair<int ,int>> vp;
    DSU(int n)
    {
        e.assign(n ,-1);
        for(int i = 0 ; i < n ; i++)
            vp.push_back({tin[i] , tout[i]});
    }
    int get(int x)
    {
        return (e[x] < 0 ? x : e[x] = get(e[x]));
    }
    bool is_good(int x)
    {
        x= get(x);
        pair<int, int> p = vp[x];
        return ((p.second - p.first + 1) == (-e[x]));
    }
    void unite(int u , int v)
    {
        u = get(u);
        v = get(v);
        if(u == v)
            return ;
        if(e[u] > e[v])
            swap(u , v);
        vp[u].first = min(vp[u].first , vp[v].first);
        vp[u].second = max(vp[u].second , vp[v].second);
        vp[v] = vp[u];
        e[u]+=e[v];
        e[v] = u;
    }
};
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<int> occ(N);
    set<int> diff;
    vector<DSU> vd(M , DSU(N));
    for(int i = 0 ; i < N - 1 ; i++)
    {
        for(int j = 0 ; j < M ; j++)
        {
            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]]++;
        }
        for(int j = 0 ; j < M ; j++)
        {
            if(vd[j].e[vd[j].get(F[S[j][i]])] != -1)
            {
                vd[j].unite(S[j][i] , F[S[j][i]]);
            }
        }
        if(diff.empty())
        {
            bool acc = 0;
            for(int j = 0 ; j < M ; j++)
            {
                if(!vd[j].is_good(S[j][i]))
                {
                    continue;
                }
                bool ok = 1;
                for(int k = 0 ; k < M ; k++)
                {
                    if(!vd[k].is_good(S[j][i]))
                    {
                        ok = 0;
                        break;
                    }
                }
                if(ok)
                {
                    acc = 1;
                    break;
                }
            }
            if(acc)
                d++;
        }
        for(int j = 0 ; j < M ; j++)
        {
            vd[j].unite(S[j][i] , F[S[j][i]]);
        }
    }
    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