Submission #1196542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196542		b00legen	9월 (APIO24_september)	C++17	100 / 100	144 ms	19904 KiB

september

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

const int N_max = 1e5;
int l[N_max], r[N_max];
vector<int>g[N_max];

void dfs(int v = 0, int p = -1) {
	if (p != -1)
	l[v] = min(l[v], l[p]);
	for (int i = 0; i < g[v].size(); i++) {
		int to = g[v][i];
		dfs(to, v);
		r[v] = max(r[v], r[to]);
	}
}

int solve(int N, int M, vector<int>F, vector<vector<int> >S) {
	for (int i = 0; i < N; i++) {
		l[i] = N;
		r[i] = 0;
	}
	for (int i = 1; i < N; i++)
	g[F[i]].push_back(i);
	for (int j = 0; j < M; j++) {
		for (int i = 0; i < N - 1; i++) {
			int nm = S[j][i];
			l[nm] = min(l[nm], i + 1);
			r[nm] = max(r[nm], i + 1);
		}
	}
	dfs();
	int res = 0;
	vector<pair<int, int>>line(N - 1);
	for (int i = 1; i < N; i++)
	line[i - 1] = {l[i], r[i]};
	sort(line.begin(), line.end());
	int cur = 0;
	for (int i = 0; i < N - 1; i++) {
		if (line[i].first > cur)
		res++;
		cur = max(cur, line[i].second);
	}
	for (int i = 0; i < N; i++)
	g[i].clear();
	return res;
}

• 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