Submission #1202536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202536		raul2008487	September (APIO24_september)	C++20	100 / 100	98 ms	16832 KiB

september

#include<bits/stdc++.h>
#include "september.h"
#define ll int
#define pb push_back
#define in insert
#define fi first
#define se second
#define vl vector<ll>
#define all(v) v.begin(), v.end()
#define endl '\n'
using namespace std;
const int sz = 1e5 + 5;
vl e[sz];
ll pos[sz], deg[sz], fr[sz], cnt, n, m;
void relax(ll node){
    for(auto to: e[node]){
        relax(to);
        pos[node] = max(pos[node], pos[to]);
    }
    // cout << "# " << node << ' ' << pos[node] << endl;
}
void add(ll x){
    if(!fr[x]){cnt ++;}
    fr[x] ++;
    if(fr[x] == m){cnt --;}
}
void init(ll n){
    for(int i = 0; i <= n; i++){
        e[i].clear();
        deg[i] = fr[i] = 0;
    }
    cnt = 0;
}
int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
    int i, j, ans = 0, bar = 0;
    n = N, m = M;
    vector<ll> deg(n + 1, 0);
    init(n);
    for(i = 1; i < n; i++){
        deg[F[i] + 1] ++;
        e[F[i] + 1].pb(i + 1);
    }
    for(i = 0; i < n - 1; i++){
        pos[S[0][i] + 1] = i;
    }
    relax(1);
    for(i = 0; i < n - 1; i++){
        for(j = 0; j < m; j++){
            add(S[j][i] + 1);
        }
        bar = max(bar, pos[S[0][i] + 1]);
        // cout << cnt << ' ' << bar << endl;
        if((!cnt) && (bar <= i)){
            ans ++;
        }
    }
    return ans;


}
/*
1
5 2
0 0 1 1
1 2 3 4
4 1 2 3
*/

• 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