Submission #1032105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032105		ToroTN	September (APIO24_september)	C++17	100 / 100	112 ms	13940 KiB

september

//#include "stub.cpp"
#include<bits/stdc++.h>
using namespace std;
#include "september.h"
#include <vector>
int n,m,p[100005],order[6][100005],st,l[100005],r[100005],par[100005],num[100005];
set<int> s[6];
int f(int a)
{
    if(par[a]==a)return a;
    return par[a]=f(par[a]);
}
void un(int b,int c)
{
    num[f(c)]+=num[f(b)];
    par[f(b)]=f(c);
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) 
{
	n=N,m=M;
    for(int i=1;i<=n;i++)
    {
        p[i-1]=F[i-1];
    }
    for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)order[i][j]=S[i-1][j-1];
    // for(int i=1;i<n;i++)printf("%d ",p[i]);
    // printf("\n");
    // for(int i=1;i<=m;i++)
    // {
    //     printf("%d\n",i);
    //     for(int j=1;j<=n-1;j++)printf("%d ",order[i][j]);
    //     printf("\n");
    // }
    int sz=1;
    st=1;
    while(st<n)
    {
        for(int i=st;i<n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                s[j].insert(order[j][i]);
            }
            int kmp=0;
            for(int j=2;j<=m;j++)if(s[j]==s[1])++kmp;
            if(kmp==m-1)
            {
                l[sz]=st;
                r[sz]=i;
                st=i+1;
                for(int j=1;j<=m;j++)s[j].clear();
                ++sz;
                break;
            }
        }
    }
    --sz;
    /*printf("%d\n",sz);
    for(int i=1;i<=sz;i++)printf("%d %d\n",l[i],r[i]);*/
    int target=1,ans=0;
    for(int i=0;i<n;i++)par[i]=i,num[i]=1;
    for(int i=sz;i>=1;i--)
    {
        target+=(r[i]-l[i]+1);
        for(int j=l[i];j<=r[i];j++)
        {
            un(order[1][j],p[order[1][j]]);
        }
        if(num[f(0)]==target)++ans;
    }
    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