This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
* author: NimaAryan
* created: 2024-08-17 20:59:09
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#endif
using i64 = long long;
constexpr int SQ = 300;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M, Q;
cin >> N >> M >> Q;
vector<vector<int>> g(N + 1);
for (int i = 0; i < M; ++i) {
int s, e;
cin >> s >> e;
--s, --e;
g[e].push_back(s);
}
vector<vector<pair<int, int>>> f(N);
for (int x = 0; x < N; ++x) {
vector<pair<int, int>> cf{{-1, x}};
for (int y : g[x]) {
cf.insert(cf.end(), f[y].begin(), f[y].end());
}
sort(cf.begin(), cf.end(), greater<>());
unordered_set<int> ex;
for (int i = 0; i < cf.size() && f[x].size() < SQ; ++i) {
auto [d, s] = cf[i];
d += 1;
if (ex.count(s)) {
continue;
}
ex.insert(s);
f[x].emplace_back(d, s);
}
}
while (Q--) {
int t, y;
cin >> t >> y;
--t;
unordered_set<int> ex;
for (int i = 0; i < y; ++i) {
int c;
cin >> c;
--c;
ex.insert(c);
}
if (y >= SQ) {
vector<int> dp(t + 1);
for (int x = 0; x <= t; ++x) {
dp[x] = ex.count(x) ? -N : 0;
for (int y : g[x]) {
dp[x] = max(dp[x], dp[y] + 1);
}
}
cout << max(-1, dp[t]) << "\n";
continue;
}
int ans = -1;
for (auto [d, s] : f[t]) {
if (!ex.count(s)) {
ans = max(ans, d);
}
}
cout << ans << "\n";
}
return 0;
}
Compilation message (stderr)
bitaro.cpp: In function 'int main()':
bitaro.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (int i = 0; i < cf.size() && f[x].size() < SQ; ++i) {
| ~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |