제출 #1204483

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1204483		Trn115	파일 삭제 (GA3_delete)	C++20	75 / 120	143 ms	327680 KiB

delete

#include <bits/stdc++.h>

#define fi first
#define se second
#define all(x) x.begin(), x.end()

using namespace std;

constexpr int inf = 1e9;

int DeletePlan( int N, int M, int K, int *A, int *B) {
	int n = N + M;
	vector<vector<int>> g(n);
	for (int i = 0; i < N; ++i) {
		g[A[i] + N].push_back(i);
	}
	for (int i = 1; i < M; ++i) {
		g[B[i] + N].push_back(i + N);
	}

	vector<int> num(n), tail(n), euler(n + 1);
	vector<vector<int>> back(n + 1);
	int timer = 0;
	function<void(int)> dfs = [&](int v) {
		num[v] = tail[v] = ++timer;
		euler[timer] = v;
		for (int u : g[v]) dfs(u);
		tail[v] = timer;
		back[tail[v]].push_back(num[v]);
	};
	dfs(N);

	vector<int> pref(n + 1);
	for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + (euler[i] < N);

	vector<vector<int>> dp(n + 1, vector<int>(K + 1, inf));
	for (int i = 0; i <= n; ++i) dp[i][0] = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= K; ++j) {
			dp[i][j] = dp[i - 1][j];
			for (int x : back[i]) {
				int val = pref[i] - pref[x - 1];
				if (val > j) continue;
				dp[i][j] = min(dp[i][j], dp[x - 1][j - val] + 1);
			}
		}
	}
	
	return dp[n][K];
}

• Subtask 1: 15 / 15
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 0 / 45