| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1281619 | KickingKun | Bitaro’s Party (JOI18_bitaro) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define bigint __int128
#define emb emplace_back
#define pb push_back
#define pii pair <int, int>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define Task ""
#define MASK(k) (1ull << k)
#define bitcnt(k) __builtin_popcount(k)
#define testBit(n, k) ((n >> k) & 1)
#define flipBit(n, k) (n ^ (1ll << k))
#define offBit(n, k) (n & ~MASK(k))
#define onBit(n, k) (n | (1ll << k))
template <class T> bool minimize(T &a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool maximize(T &a, T b) {if (a < b) {a = b; return true;} return false;}
const int N = 1e5 + 5, lim = 60, mod = 1e9 + 7;
const ll INF = 1e18;
int n, m, q, t[N];
vector <int> to[N], ban[N];
namespace sub12 {
void solve() {
for (int i = 0; i < q; i++) {
vector <int> dp(t[i] + 1, 0);
for (int &x: ban[i]) dp[x] = -1e9;
for (int u = 1; u <= t[i]; u++) {
for (int v: to[u]) maximize(dp[u], dp[v] + 1);
}
cout << (dp[t[i]] < 0 ? -1 : dp[t[i]]) << '\n';
}
}
}
namespace sub3 {
const int BLOCK = 100;
vector <pii> candidate[N];
void solve() {
bitset <N> mark; mark.reset();
for (int u = 1; u <= n; u++) {
for (int v: to[u]) {
if (candidate[u].empty()) candidate[u] = candidate[v];
else {
vector <pii> merge; int l = 0, r = 0;
while (l < candidate[u].size() && r < candidate[v].size()) {
if (merge.size() == BLOCK) break;
if (mark.test(candidate[u][l].se)) ++l;
else if (mark.test(candidate[v][r].se)) ++r;
else if (candidate[u][l] > candidate[v][r]) {
mark.set(candidate[u][l].se);
merge.emplace_back(candidate[u][l++]);
}
else {
mark.set(candidate[v][r].se);
merge.emplace_back(candidate[v][r++]);
}
}
while (merge.size() < BLOCK && l < candidate[u].size()) {
if (mark.test(candidate[u][l].se)) ++l;
else merge.emplace_back(candidate[u][l++]);
}
while (merge.size() < BLOCK && r < candidate[v].size()) {
if (mark.test(candidate[v][r].se)) ++r;
merge.emplace_back(candidate[v][r++]);
}
candidate[u] = merge;
for (auto [d, v]: candidate[u])
mark.reset(v);
}
}
for (int i = 0; i < candidate[u].size(); i++) ++candidate[u][i].fi;
if (candidate[u].size() < BLOCK)
candidate[u].emplace_back(0, u);
}
return;
// for (int u = 1; u <= n; u++) {
// cerr << u << ": ";
// for (auto [d, v]: candidate[u])
// cerr << "(" << d << ' ' << v << "), ";
// cerr << '\n';
// }
mark.reset();
for (int i = 0; i < q; i++) {
// |ban[i]| <= t[i] -> |ban[i]| <= |candidate[t[i]] chua opt
if (ban[i].size() < candidate[t[i]].size()) {
// |ban[i]| < |candidate[t[i]]|
int ans;
for (int &x: ban[i]) mark.set(x);
for (auto [d, u]: candidate[t[i]]) {
if (!mark.test(u)) {
ans = d; break;
}
}
for (int &x: ban[i]) mark.reset(x);
cout << ans << '\n';
}
else {
for (int u = 1; u <= t[i]; i++) dp[u] = 0;
for (int &u: ban[i]) dp[u] = -1e9;
for (int u = 1; u <= t[i]; u++) {
for (int v: to[u]) maximize(dp[u], dp[v] + 1);
}
cout << (dp[t[i]] < 0 ? -1 : dp[t[i]]) << '\n';
}
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
if (fopen(Task".inp", "r")) {
freopen(Task".inp", "r", stdin);
freopen(Task".out", "w", stdout);
}
cin >> n >> m >> q;
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
to[v].emplace_back(u);
}
for (int i = 0; i < q; i++) {
int sz; cin >> t[i] >> sz;
ban[i].assign(sz, 0);
for (int &x: ban[i]) cin >> x;
while (!ban[i].empty() && ban[i].back() > t[i]) ban[i].pop_back();
}
sub3::solve();
}