Submission #1218044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218044		urosk	September (APIO24_september)	C++20	59 / 100	329 ms	41700 KiB

september

#include "september.h"
#include "bits/stdc++.h"
#define fi first
#define sc second
#define here cerr<<"=====================================\n"
#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;
}
vector<ll> g[maxn];
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
    n = N,m = M;
    for(ll i = 0;i<N;i++) par[i] = F[i];
    //for(ll i = 1;i<=n;i++)
    par[1] = 1;
    n--;
    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;
        //dfs(0);
        s[j].clear();
        for(ll i = 1;i<=n;i++) s[j].insert({i,i});
        for(ll i = 1;i<=n;i++){
            if(par[i]&&id[j][i]>id[j][par[i]]){
                ll l = id[j][par[i]],r = id[j][i];
                auto it = s[j].upper_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],id[k][a[j][i]]);
            }
        }
    }
    ll ans = 0;
    for(ll j = 1;j<=m;j++) cur[j] = 0;
    while(1){
        bool novi = 1;
        for(ll j = 1;j<m;j++) novi&=cur[j]==cur[j+1];
        if(novi){
            if(cur[1]==n) break;
            ans++;
            for(ll j = 1;j<=m;j++) cur[j] = f(j,cur[j]+1);
            continue;
        }
        for(ll j = 1;j<=m;j++) ncur[j] = cur[j];
        for(ll j = 1;j<=m;j++){
            for(ll k = 1;k<=m;k++){
                if(j==k) continue;
                ncur[k] = max(ncur[k],f(k,pf[j][k][cur[j]]));
            }
        }
        for(ll j = 1;j<=m;j++) cur[j] = ncur[j];
    }
    for(ll i = 0;i<=n;i++) g[i].clear();
    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 0 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 9 / 9
• Subtask 10: 0 / 16