| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1203091 | monstermceldritch | September (APIO24_september) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vii;
int solve(int n, int m, vector<int> f, vector<vector<int>> s)
{
vii children(n, vi());
for (int i = 1; i < n; i++)
children[f[i]].push_back(i);
vector<bool> done(n, false);
vector<pair<int, int>> earlyandlate(n - 1, pair<int, int>(make_pair(n, -1)));
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < m; j++)
{
int cur = s[j][i];
earlyandlate[cur].first = min(earlyandlate[cur].first, i);
earlyandlate[cur].second = max(earlyandlate[cur].second, i);
}
}
int threshold = 0, ans = 0;
for (int i = 0; i < n - 1; i++)
{
for (int l = 0; l < m; l++)
{
if (earlyandlate[s[l][i]].second > threshold)
{
for (int j = threshold + 1; j < earlyandlate[s[l][i]].second; j++)
{
for (int k = 0; k < m; k++)
done[s[k][j]] = true;
}
threshold = earlyandlate[s[l][i]].second;
}
for (auto j : children[s[l][i]])
{
if (!done[j])
{
for (int k = max(i + 1, threshold + 1); k < n - 1; k++)
{
bool over = false;
for (int a = 0; a < m; a++)
{
done[s[a][k]] = true;
if (s[a][k] == j)
{
threshold = k;
over = true;
}
}
if (over)
break;
}
}
}
done[s[l][i]] = true;
}
if (i >= threshold)
ans++;
}
return ans;
}
int main()
{
cout << solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4, 1, 2, 3}});
return 0;
}