제출 #1218057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218057		urosk	September (APIO24_september)	C++20	100 / 100	635 ms	55060 KiB

september

#include "september.h"
#include "bits/stdc++.h"
#define fi first
#define sc second
#define here cerr<<"=====================================\n"
#define pb push_back
#define ceri(a_,l_,r_) {for(ll i_ = l_;i_<=r_;i_++) cerr<<a_[i_]<< " ";cerr<<endl;}
using namespace std;

using ll = int;
using pll = pair<ll,ll>;
const ll maxn = 100005;
ll n,m;
ll par[maxn];
set<pll> s[6];
ll a[6][maxn];
ll id[6][maxn];
ll pf[6][6][maxn];
ll cur[6];
ll ncur[6];
/**
2
5 2
0 0 1 1
1 2 3 4
4 1 2 3
3 1
0 0
1 2
**/
ll f(ll j,ll i){
    auto it = s[j].lower_bound({i,n+1}); it = prev(it);
    return (*it).sc;
}

ll sub[maxn];
vector<ll> g[maxn];
ll curj = 0;
void dfs(ll u){
    sub[u] = id[curj][u];
    for(ll s : g[u]){
        dfs(s);
        sub[u] = max(sub[u],sub[s]);
    }
}

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
    n = N-1,m = M;
    for(ll i = 0;i<N;i++) par[i] = F[i],g[par[i]].pb(i);
    //for(ll i = 1;i<=n;i++)
    for(ll j = 1;j<=m;j++){
        for(ll i = 1;i<=n;i++) a[j][i] = S[j-1][i-1];
        for(ll i = 1;i<=n;i++) id[j][a[j][i]] = i;
        curj = j;
        dfs(0);
        s[j].clear();
        for(ll i = 1;i<=n;i++) s[j].insert({i,i});
        for(ll i = 1;i<=n;i++){
            ll l = id[j][i],r = sub[i];
            auto it = s[j].lower_bound({l,n+1}); it = prev(it);
            while((*it).sc<r){
                auto it2 = next(it);
                pll p = {(*it).fi,(*it2).sc};
                s[j].erase(s[j].find(*it));
                s[j].erase(s[j].find(*it2));
                s[j].insert(p);
                it = s[j].find(p);
            }
        }
    }
    for(ll j = 1;j<=m;j++){
        for(ll k = 1;k<=m;k++){
            for(ll i = 1;i<=n;i++){
                pf[j][k][i] = max(pf[j][k][i-1],f(k,id[k][a[j][i]]));
                pf[j][k][i] = max(pf[j][k][i],i);
            }
        }
    }
    ll ans = 0;
    for(ll i = 1;i<=n;i++){
        bool ok = 1;
        for(ll j = 1;j<=m;j++){
            for(ll k = 1;k<=m;k++){
                if(pf[j][k][i]!=i) ok = 0;
            }
        }
        if(ok) ans++;
    }
    for(ll i = 0;i<=n;i++) g[i].clear(),par[i] = 0;
    for(ll j = 0;j<=m;j++) s[j].clear();
    for(ll j = 0;j<=m;j++){
        for(ll k = 0;k<=m;k++){
            for(ll i = 0;i<=n;i++) pf[j][k][i] = 0;
        }
        for(ll i = 0;i<=n;i++) a[j][i] = id[j][i] = 0;
    }
    return ans;
}

• 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