Submission #1081496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081496		dong_gas	September (APIO24_september)	C++17	11 / 100	2 ms	2908 KiB

september

#include <bits/extc++.h>
#include "september.h"
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
using namespace __gnu_pbds;
template<class T> using PBDS = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using multiPBDS = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll n;
ll mini[100201], maxi[100201];
vector<ll> adj[100201];

void dfs(ll u) {
    for(ll& v:adj[u]) {
        dfs(v);
        maxi[u]=max(maxi[u],maxi[v]);
    }
}

int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
    for(int i=0;i<N;i++) adj[i].clear(), mini[i]=1e9, maxi[i]=-1;
    for(int i=1;i<N;i++) adj[F[i]].push_back(i);
    for(int j=0;j<M;j++) {
        for(int i=0;i<N-1;i++) {
            mini[S[j][i]]=min(mini[S[j][i]],(ll)i+1);
            maxi[S[j][i]]=max(maxi[S[j][i]],(ll)i+1);
        }
    }
    dfs(0);
    ll ans=0, b=0;
    vector<pll> v;
    for(ll i=1;i<N;i++) v.push_back({mini[i],maxi[i]});
    sort(all(v),[&](pll x, pll y) {
            return x.second<y.second;
    });
    for(auto& [l, r]:v) {
        if(b<l) ans++, b=r;
        else b=max(b,r);
    }
	return ans;
}

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