Submission #1081499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081499		dong_gas	September (APIO24_september)	C++17	100 / 100	173 ms	24412 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, p=0, q=0;
    vector<pll> v;
    for(ll i=1;i<N;i++) v.push_back({mini[i],maxi[i]});
    sort(all(v));
    for(auto& [l, r]:v) {
        if(q<l) ans++, p=l, q=r;
        else q=max(q,r);
    }
	return ans;
}

Compilation message (stderr)

september.cpp: In function 'int solve(int, int, std::vector<int>, std::vector<std::vector<int> >)':
september.cpp:35:15: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   35 |     ll ans=0, p=0, q=0;
      |               ^

• 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