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;
#define pii pair<int, int>
int N = 300;
int main()
{
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> graph(n);
vector<vector<pii>> best(n);
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
a--; b--;
graph[a].push_back(b);
}
vector<int> done(n, 0);
for (int i = 0; i < n; i++)
{
best[i].push_back({0, i});
sort(best[i].begin(), best[i].end(), greater<pii>());
vector<pii> nb;
for (pii ele:best[i])
{
if (done[ele.second]) continue;
if (nb.size()==N) break;
done[ele.second] = 1;
nb.push_back(ele);
}
best[i] = nb;
for (int ele:graph[i])
{
for (pii ele2:best[i]) best[ele].push_back({ele2.first+1, ele2.second});
}
for (pii ele:best[i]) done[ele.second] = 0;
}
vector<int> usable(n, 1);
while (q--)
{
int x, c;
cin >> x >> c;
x--;
vector<int> nused(c);
for (int i = 0; i < c; i++)
{
cin >> nused[i];
nused[i]--;
usable[nused[i]]=0;
}
if (c > N)
{
int mx = -1;
vector<int> dist(n, -1e9);
dist[x] = 0;
for (int j = x-1; j >= 0; j--)
{
for (int ele:graph[j])
{
dist[j] = max(dist[j], dist[ele]+1);
}
if (usable[j]) mx = max(mx, dist[j]);
}
cout << mx << "\n";
}
else
{
int b = 0;
for (pii ele:best[x])
{
if (usable[ele.second])
{
cout << ele.first << "\n";
b=1;
break;
}
}
if (!b) cout << -1 << "\n";
}
for (int ele:nused) usable[ele] = 1;
}
return 0;
}
Compilation message (stderr)
bitaro.cpp: In function 'int main()':
bitaro.cpp:32:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
32 | if (nb.size()==N) break;
| ~~~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |