#include "september.h"
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <climits>
#include <bitset>
#include <vector>
#include <queue>
#include <set>
#define bset std::bitset<100005>
using namespace std;
void dfs(bset& S, vector<int>& P, int N, vector<vector<int>>& O) {
if (S[N]) return;
S[N] = 1;
if (P[N] != -1)
O[P[N]].push_back(N), dfs(S, P, P[N], O);
}
void add_childs(vector<vector<int>>& C, int N, bset& target, bset& rem, int& top) {
++top;
target[N] = 1;
for (int c: C[N]) {
if (target[c]) continue;
add_childs(C, c, target, rem, top);
}
}
int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
vector<vector<int>> childs(N);
vector<pair<int, bset>> members(M, {0, bset()});
bset dfsStorage;
for (int x = 0; x < N; x++)
dfs(dfsStorage, F, x, childs);
bset target;
int top = 0, days = 0;
do {
{
int node = S[0][top];
members[0].second[node] = 1;
for (int c: childs[node]) {
if (target[c]) continue;
add_childs(childs, c, target, members[0].second, top);
}
target[node] = 1;
}
top++;
do {
for (int r = 0; r < M; r++) {
int& rtop = members[r].first;
while (rtop < top) {
int node = S[r][rtop++];
members[r].second[node] = 1;
for (int c: childs[node]) {
if (target[c]) continue;
add_childs(childs, c, target, members[r].second, top);
}
if (target[node]) continue;
top++, target[node] = 1;
}
}
} while (members[0].first != members[M - 1].first);
days++;
} while (1 + top < N);
return days;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |