| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1054265 | manhlinh1501 | Bitaro’s Party (JOI18_bitaro) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using i64 = long long;
const int MAXN = 2e5 + 5;
const int BLOCK_SIZE = 200;
#define ALL(a) (a).begin(), (a).end()
int N, M, Q;
vector<int> adj[MAXN];
vector<int> radj[MAXN];
bool is_deleted[MAXN];
vector<pii> dp[MAXN];
int dist[MAXN];
bool f[MAXN];
vector<pii> merge_vector(vector<pii> a, vector<pii> b) {
int x = 0, y = 0;
for(auto &[x, y] : b)
x++;
vector<pii> ans;
while(x < a.size() and y < b.size() and ans.size() < BLOCK_SIZE) {
if(a[x].first > b[y].first)
ans.emplace_back(a[x++]);
else
ans.emplace_back(b[y++]);
}
while(x < a.size() and ans.size() < BLOCK_SIZE)
ans.emplace_back(a[x++]);
while(y < b.size() and ans.size() < BLOCK_SIZE)
ans.emplace_back(b[y++]);
return ans;
}
signed main() {
#define TASK "code"
if (fopen(TASK ".inp", "r")) {
freopen(TASK ".inp", "r", stdin);
freopen(TASK ".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M >> Q;
for(int i = 1; i <= M; i++) {
int u, v;
cin >> u >> v;
adj[u].emplace_back(v);
radj[v].emplace_back(u);
}
for(int u = 1; u <= N; u++) {
dp[u].emplace_back(0, u);
for(int v : radj[u])
dp[u] = merge(dp[u], dp[v]);
}
while(Q--) {
int u;
cin >> u;
int sz;
cin >> sz;
vector<int> a(sz, 0);
for(int &x : a) cin >> x;
for(int x : a) is_deleted[x] = true;
if(a.size() >= BLOCK_SIZE) {
int ans = -1;
for(int i = 1; i <= N; i++) dist[i] = -1;
dist[1] = 0;
for(int i = 2; i <= N; i++) {
for(int v : radj[i])
dist[i] = max(dist[i], dist[v] + 1);
}
cout << dist[u] << "\n";
} else {
int ans = -1;
for(auto [x, y] : dp[u]) {
if(is_deleted[y] == false) ans = max(ans, x);
}
cout << ans << "\n";
}
for(int x : a) is_deleted[x] = false;
}
return (0 ^ 0);
}