Submission #1000182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000182		Evirir	September (APIO24_september)	C++17	100 / 100	247 ms	16852 KiB

september

#include "september.h"

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
//template<typename T>
//using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
template<typename T> void amax(T &a, T b){ a=max(a,b); }
template<typename T> void amin(T &a, T b){ a=min(a,b); }

#define sz(x) (int)(x).size()

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
	int ans = 0;
	unordered_set<int> s;
	unordered_set<int> bad;  // parent in s but itself not in s
	vector<vector<int>> adj(N);
	for (int i = 1; i < sz(F); i++)
	{
		adj[F[i]].pb(i);
	}

	for (int i = 0; i < N - 1; i++)
	{
		for (const auto& vec : S)
		{
			int u = vec[i];
			if (s.count(u)) continue;
			s.insert(u);

			// add bad nodes
			for (int v : adj[u])
			{
				if (!s.count(v)) bad.insert(v);
			}

			// remove self from bad nodes
			if (s.count(F[u]))
			{
				assert(bad.count(u));
				bad.erase(u);
			}
		}
		if (sz(s) == i + 1 && bad.empty())
			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