Submission #1078551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078551		Marceantasy	September (APIO24_september)	C++17	100 / 100	112 ms	19604 KiB

september

#include <bits/stdc++.h>
#include "september.h"
using namespace std; 

#define ll long long
#define ar array
#define rep(i, n) for(int i = 0; i<(int)n; ++i)

const int mxN = 2e5+5, M = 1e9+7;
int ans[mxN];
vector<int> adj[mxN];

void init(int n){
	rep(i, n){
		ans[i] = 0;
		adj[i].clear();
	}
}

int solve(int N, int M, vector<int> F, vector<vector<int>> S){
	init(N);
	rep(i, N-1){
		adj[F[i+1]].push_back(i+1);
	}
	for(vector<int> &v : S){
		vector<int> status(N);
		int bad = 0;
		int ff = 0;
		v.push_back(0);
		reverse(v.begin(), v.end());
		vector<int> f(N);
		rep(j, N){ 
			f[v[j]] = 1;
			if(v[j] > 0 && f[F[v[j]]] == 0) bad++;
			for(auto ve : adj[v[j]]){
				if(f[ve] == 1) bad--;
			}			
			if(status[v[j]] != 0) ff--;		
			status[v[j]]++;
			if(status[v[j]] != 0) ff++;
			if(status[S[0][j]] != 0) ff--;
			status[S[0][j]]--;
			if(status[S[0][j]] != 0) ff++;
			
			if(bad == 0 && ff == 0){
				ans[j]++;
			}
		}

	}
	return count(ans, ans+N, M) -1;
}

// int main(){
// #ifdef _DEBUG
// //	freopen("input.txt", "r", stdin);
// //	freopen("output.txt", "w", stdout);
// #endif
//     std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(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