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;
int N, M, Q;
vector<vector<int>> adj, revAdj;
vector<int> memo;
int goal;
int dp(int pos) {
if (pos > goal) return INT_MIN;
if (pos == goal) return 0;
if (memo[pos] != -1) return memo[pos];
int ans = INT_MIN;
for (int x : adj[pos]) {
ans = max(ans, dp(x) + 1);
}
return memo[pos] = ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M >> Q;
adj.resize(N); revAdj.resize(N);
for (int i = 0; i < M; i++) {
int a, b; cin >> a >> b; a--; b--;
adj[a].push_back(b);
revAdj[b].push_back(a);
}
vector<vector<int>> busy(Q);
vector<bool> dec(Q, false);
vector<int> T(Q);
for (int i = 0; i < Q; i++) {
cin >> T[i]; T[i]--;
int Y; cin >> Y;
for (int j = 0; j < Y; j++) {
int a; cin >> a; a--;
busy[i].push_back(a);
}
if (Y < sqrt(N) - 230) dec[i] = true;
}
vector<vector<pair<int,int>>> sol(N);
for (int i = 0; i < N; i++) {
vector<int> it(int(revAdj[i].size()), 0);
for (int k = 0; k < sqrt(N) - 230; k++) {
pair<int,int> best = {INT_MAX, -1};
int index = -1;
for (int j = 0; j < int(revAdj[i].size()); j++) {
if (it[j] < sol[j].size() && sol[j][it[j]] < best) {
best = sol[j][it[j]];
best.first--;
index = j;
}
}
if (index != -1) {
it[index]++;
sol[i].push_back(best);
}
}
sol[i].push_back({0,i});
}
for (int i = 0; i < Q; i++) {
if (!dec[i]) {
goal = T[i];
memo.clear(); memo.resize(T[i], -1);
int ans = -1;
for (int j = 0; j <= goal; j++) {
auto it = lower_bound(busy[i].begin(), busy[i].end(), j);
if (it == busy[i].end() || (*it) != j) ans = max(ans, dp(j));
}
cout << ans << '\n';
}
else {
bool ok = false;
for (auto x : sol[T[i]]) {
auto it = lower_bound(busy[i].begin(), busy[i].end(), x.second);
if (it == busy[i].end() || (*it) != x.second) {
ok = true;
cout << -x.first << '\n';
break;
}
}
if (!ok) cout << -1 << '\n';
}
}
return 0;
}
Compilation message (stderr)
bitaro.cpp: In function 'int main()':
bitaro.cpp:55:16: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | if (it[j] < sol[j].size() && sol[j][it[j]] < best) {
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |