Submission #1247538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247538		ASGA_RedSea	September (APIO24_september)	C++20	100 / 100	124 ms	21164 KiB

september

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#include "september.h"

using namespace std;
using ll = long long;


void calc(int i,vector <vector <int>>& a,vector <int>& p,vector <int>& g){
    if(i > 0)g[i] = max(g[i],p[i]);
    for(const auto& j : a[i]){
        calc(j,a,p,g);

        if(i > 0)g[i] = max(g[i],g[j]);
    }
}

int solve(int n,int m,vector <int> f,vector <vector <int>> s){
    vector <vector <int>> a(n);
    for(int i = 1;i < n;i++){
        a[f[i]].push_back(i);
    }

    vector <vector <int>> p(m,vector <int> (n,0));
    for(int i = 0;i < m;i++){
        for(int j = 0;j < n - 1;j++){
            p[i][s[i][j]] = j;
        }
    }

    vector <vector <int>> g(m,vector <int> (n,0));
    for(int i = 0;i < m;i++){
        calc(0,a,p[i],g[i]);
    }

    int lstd = 0,pl = 0,k = 0;

    int mx = 0;

    while(lstd < n-1){
        mx = 0;
        while(1){
            for(int i = 0;i < m;i++){
                for(int j = pl;j < n-1;j++){
                    mx = max(mx,g[i][s[i][j]]);
                    if(j == mx){
                        mx = 0;
                        for(int h = pl;h <= j;h++)mx = max(mx,g[(i + 1) % m][s[i][h]]);
                        break;
                    }
                }
            }

            if(mx == lstd)break;
            lstd = mx;
        }

        lstd++;
        pl = lstd;
        k++;
    }

    return k;
}

• 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