이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1e5+10, MOD = 998244353;
const int B = 200;
int n, m, q;
vector<int> adj[N];
vector<pair<int, int>> best[N]; // sorted from biggest to smallest
void merge_into(vector<pair<int, int>>& one, const vector<pair<int, int>>& two) {
vector<pair<int, int>> ans;
int p1 = 0, p2 = 0;
auto move_one = [&]() {
ans.push_back(one[p1++]);
};
auto move_two = [&]() {
ans.push_back(two[p2++]);
};
while (sz(ans) < B && (p1 < sz(one) || p2 < sz(two))) {
if (p1 == sz(one)) move_two();
else if (p2 == sz(two)) move_one();
else if (one[p1] > two[p2]) move_one();
else move_two();
}
one = ans;
}
int dp[N];
bool bad[N];
void solve() {
cin >> n >> m >> q;
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b, --a, --b;
adj[b].push_back(a);
}
for (int i = 0; i < n; i++) {
for (int nxt : adj[i]) {
merge_into(best[i], best[nxt]);
}
for (auto& [x, c] : best[i]) x++;
best[i].emplace_back(0, i);
while (sz(best[i]) > B) best[i].pop_back();
}
while (q--) {
int c, k; cin >> c >> k, --c;
if (k < B) {
vector<int> v(k);
for (auto& x : v) cin >> x, --x;
for (int x : v) bad[x] = 1;
int ans = -1;
for (auto [x, i] : best[c]) if (!bad[i]) {
ans = max(ans, x);
}
for (int x : v) bad[x] = 0;
cout << ans << '\n';
} else {
memset(dp, 0, sizeof(dp));
for (int i = 0; i < k; i++) {
int x; cin >> x, --x;
dp[x] = -MOD;
}
for (int i = 0; i < n; i++) {
for (int nxt : adj[i]) {
dp[i] = max(dp[i], dp[nxt] + 1);
}
}
cout << (dp[c] < 0 ? -1 : dp[c]) << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |