#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];
ll dsu[6][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;
}
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+1] = F[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;
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;
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];
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |