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;
const int N = 1e5;
int n, m, q;
vector<int> adj[N];
vector<pair<int, int>> far[N];
void pre() {
bool allowed[n];
fill(allowed, allowed + n, true);
for (int i = 0; i < n; i++) {
int p[adj[i].size()] = {};
int count = 0;
vector<int> used;
while (count <= ceil(sqrt(n))) {
pair<pair<int, int>, int> ans = {{-1, -1}, - 1};
for (int j = 0; j < adj[i].size(); j++) {
if (p[j] < far[adj[i][j]].size() && ans.first < far[adj[i][j]][p[j]] && allowed[far[adj[i][j]][p[j]].second])
ans = {far[adj[i][j]][p[j]], j};
}
if (ans.first.first != -1) {
far[i].emplace_back(ans.first.first + 1, ans.first.second);
p[ans.second]++;
allowed[ans.first.second] = false;
used.push_back(ans.first.second);
count++;
} else break;
}
for (int j : used)
allowed[j] = true;
if (far[i].size() <= ceil(sqrt(n)))
far[i].emplace_back(0, i);
}
}
int calc(int t, const set<int>& c) {
int dp[n] = {};
fill(dp, dp + n, -1e9);
dp[t] = 0;
for (int i = t; i >= 0; i--) {
for (int j : adj[i])
dp[j] = max(dp[j], dp[i] + 1);
}
int ans = -1;
for (int i = t; i >= 0; i--) {
if (!c.count(i))
ans = max(ans, dp[i]);
}
return ans;
}
int find(int t, const set<int>& c) {
for (auto i : far[t]) {
if (!c.count(i.second))
return i.first;
}
return -1;
}
int solveTestCase(int test) {
cin >> n >> m >> q;
for (int i = 0; i < m; i++) {
int s = 0, e = 0;
cin >> s >> e;
s--, e--;
adj[e].push_back(s);
}
pre();
for (int i = 0; i < q; i++) {
int t = 0, y = 0;
cin >> t >> y;
set<int> c;
for (int j = 0; j < y; j++) {
int temp = 0;
cin >> temp;
c.insert(temp - 1);
}
if (y >= floor(sqrt(n)))
cout << calc(t - 1, c) << "\n";
else
cout << find(t - 1, c) << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int test = 1;
//cin >> test;
for (int i = 1; i <= test; i++)
solveTestCase(i);
}
Compilation message (stderr)
bitaro.cpp: In function 'void pre()':
bitaro.cpp:20:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < adj[i].size(); j++) {
~~^~~~~~~~~~~~~~~
bitaro.cpp:21:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (p[j] < far[adj[i][j]].size() && ans.first < far[adj[i][j]][p[j]] && allowed[far[adj[i][j]][p[j]].second])
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int solveTestCase(int)':
bitaro.cpp:96:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |