| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1353924 | SulA | Bitaro’s Party (JOI18_bitaro) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define popcount __builtin_popcount
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;
const int N = 100000, S = 100;
bool busy[N];
vector<int> adj[N], rev[N];
vector<pair<int,int>> biggest[N];
int dp[N];
vector<pair<int,int>> merge(const vector<pair<int,int>>& A, const vector<pair<int,int>>& B) {
vector<pair<int,int>> res;
int n = A.size(), m = B.size();
res.reserve(n + m);
A.emplace_back(-1, -1);
B.emplace_back(-1, -1);
int i, j;
for (i = j = 0; i < n || j < m; ) {
if (A[i] > B[j]) {
res.push_back(A[i++]);
} else {
res.push_back(B[j++]);
}
}
return res;
}
void init() {
for (int i = 0; i < N; i++) {
vector<pair<int,int>> actual = {{0, i}};
actual.reserve(S*rev[i].size());
for (int j : rev[i]) {
for (auto& [dis, node] : biggest[j])
actual.emplace_back(dis + 1, node);
}
ranges::sort(actual, greater<>());
for (auto p : actual) {
auto [dis, node] = p;
if (biggest[i].size() < S && !busy[node]) {
biggest[i].push_back(p);
busy[node] = true;
}
}
for (auto [_, node] : biggest[i]) {
busy[node] = false;
}
}
}
int big(int t) {
dp[t] = 0;
int res = -busy[t];
for (int u = t-1; u >= 0; u--) {
dp[u] = -1e9;
for (int v : adj[u])
if (v <= t)
dp[u] = max(dp[u], dp[v] + 1);
if (!busy[u]) {
// cout<<u<<' '<<t<<' '<<dp[u]<<"\n";
res = max(res, dp[u]);
}
}
return res;
}
int small(int t) {
for (auto [dis, node] : biggest[t]) {
if (busy[node]) continue;
return dis;
}
return -1;
}
int query(const vector<int>& C, int t) {
for (int x : C) busy[x] = true;
int res = big(t);//C.size() < S - 2 ? small(t) : big(t);
for (int x : C) busy[x] = false;
return res;
}
int main() {
int n,m,q; cin >> n >> m >> q;
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
adj[--u].push_back(--v);
rev[v].push_back(u);
}
init();
// for (int i = 0; i < n; i++) {
// for (auto [dis, node] : biggest[i])
// cout<<dis<<' '<<node<<'\n';
// cout<<"\n";
// }
while (q--) {
int t, y; cin >> t >> y;
t--;
vector<int> C(y);
for (int& x : C) cin >> x, x--;
cout << query(C, t) << "\n";
}
}