Submission #1201232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201232		browntoad	September (APIO24_september)	C++20	100 / 100	114 ms	19976 KiB

september

#include "september.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n) 
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())

namespace{
	const ll maxn = 1e5+5;
	const ll mod = 1e9+7;
	const ll inf = 1ll<<60;

	int n, m;
	vector<vector<int>> seq;
	vector<int> pos[maxn]; // for each node, its id in the sequence
	int mxid;

	vector<int> g[maxn];
	vector<int> occ(maxn);
}

void dfs(int u){
	if (occ[u]) return;
	REP(i, m) mxid = max(mxid, pos[u][i]);
	occ[u] = 1;
	for (auto v:g[u]){
		dfs(v);
	}
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
	n = N; m = M;
	mxid = -1;
	seq = S;
	REP(i, n) g[i].clear();
	REP(i, n) occ[i] = 0;

	REP1(i, n-1){
		g[F[i]].pb(i);
	}
	REP(i, n) pos[i].clear();
	REP(i, m){
		REP(j, n-1){
			pos[S[i][j]].pb(j);
		}
	}

	int ret = 0;
	REP(j, n-1){
		if (mxid < j){
			ret++;
			REP(i, m){
				dfs(seq[i][j]); 
			}
		}
		else{
			REP(i, m) dfs(seq[i][j]);
		}
	}
	return ret;
}

• 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