이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 20, sq = 300;// 69
int n, m;
vector <int> adj[N];
vector <pair <int, int>> vec[N];
bool vis[N], seen[N];
int dp[N];
signed main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int q;
cin >> n >> m >> q;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v, u--, v--;
adj[v].push_back(u);
}
for (int i = 0; i < n; i++) {
vector <pair <int, int>> tmp;
for (auto u: adj[i])
for (auto [j, idx]: vec[u])
tmp.push_back({j + 1, idx});
sort(tmp.begin(), tmp.end(), greater <>());
for (auto [j, idx]: tmp) {
if (vec[i].size() == sq)
break;
if (seen[idx])
continue;
vec[i].push_back({j, idx}), seen[idx] = 1;
}
for (auto [j, idx]: vec[i])
seen[idx] = 0;
if (vec[i].size() < sq)
vec[i].push_back({0, i});
}
while (q--) {
int v, k;
cin >> v >> k, v--;
vector <int> tmp;
while (k--) {
int x;
cin >> x, x--, tmp.push_back(x), vis[x] = 1;
}
if (tmp.size() <= sq) {
bool fnd = 0;
for (auto [j, idx]: vec[v])
if (!vis[idx]) {
cout << j << '\n', fnd = 1;
break;
}
if (!fnd)
cout << "-1\n";
}
else {
for (int i = 0; i < n; i++) {
dp[i] = (vis[i] ? -1 : 0);
for (auto u: adj[i])
if (dp[u] != -1)
dp[i] = max(dp[i], dp[u] + 1);
}
cout << dp[v] << '\n';
}
for (auto x: tmp)
vis[x] = 0;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |