| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1366697 | ahmdnawaz | 9월 (APIO24_september) | C++20 | 0 ms | 0 KiB |
#include "september.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
vector<int> deg(N, 0);
for (int i = 1; i < N; i++) {
deg[i]++;
deg[F[i]]++;
}
for (int i = 1; i < N; i++)
deg[i]--;
vector<bool> have(n, false);
auto is_valid = [&](vector<int> vec) {
vector<int> Deg = deg;
int sm = 0;
for (int node : vec) {
if (Deg[node] == 0) {
while (1) {
if (node == 0) break;
Deg[F[node]]--;
if (Deg[F[node]] == 0) {
if (have[F[node]]) {
have[F[node]] = false;
sm -= 1;
} else {
break;
}
}
node = F[node];
}
} else {
have[F[node]] = true;
sm += 1;
}
}
if (!sm) {
deg = Deg;
}
return !sm;
};
int ans = 0;
vector<set<int>> vec(M);
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < M; j++)
vec[j].insert(S[j][i]);
bool ok = true;
for (int j = 1; j < M; j++)
if (vec[j] != vec[j - 1])
ok = false;
if (!ok) continue;
vector<int> to_check;
for (int node : vec[0])
to_check.push_back(node);
if (is_valid(to_check)) {
for (int j = 0; j < M; j++)
vec[j].clear();
ans += 1;
}
}
return ans;
}
