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;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,1:0; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,1:0; }
const int B = 320, N = 1e5;
vector<pair<int,int>> longest_dist[N];
vector<int> adj[N],radj[N];
int V[N],indices[N],dist[N];
bool banned[N],taken[N];
void solve() {
int n,m,q;
cin >> n >> m >> q;
for (int u,v;m--;) {
cin >> u >> v;
assert(u < v);
adj[--u].push_back(--v);
radj[v].push_back(u);
}
for (int i=0;i<n;i++) {
pair<int,int> best = {-1,-1};
do {
best = {-1,-1};
for (int &v: radj[i]) {
while(indices[v] < int(longest_dist[v].size())) {
if (!taken[longest_dist[v][indices[v]].second]) {
if (longest_dist[v][indices[v]].first+1 > best.first) {
best = longest_dist[v][indices[v]];
best.first++;
indices[v]++;
}
break;
}
indices[v]++;
}
}
if (best.first != -1) {
longest_dist[i].push_back(best);
taken[best.second] = true;
}
} while(best.second != -1 && longest_dist[i].size() != B);
for (int &v: radj[i]) {
indices[v] = 0;
}
for (auto &[d,node]: longest_dist[i]) {
taken[node]=false;
}
if (longest_dist[i].size() != B) {
longest_dist[i].emplace_back(0,i);
}
}
/*
for (int i=0;i<n;i++) {
cout << "Node " << i+1 << "\n";
for (auto [d,node]: longest_dist[i]) {
cout << "Dist " << d << " from node " << node+1 << "\n";
}
cout << "\n";
}
*/
for (int u,sz;q--;) {
cin >> u >> sz;
--u;
for (int i=0;i<sz;i++) {
cin >> V[i];
banned[--V[i]]=true;
}
int csz = int(longest_dist[u].size());
if (sz >= csz) {
memset(dist,-1,4*(u+1));
for (int i=0;i<=u;i++) {
if (!banned[i]) {
cmax(dist[i],0);
}
if (dist[i] != -1) {
// this node CAN be reached
for (int &v: adj[i]) {
cmax(dist[v],dist[i]+1);
}
}
}
cout << dist[u] << "\n";
} else {
int p = 0;
while(true) {
assert(p < csz);
if (!banned[longest_dist[u][p].second]) {
cout << longest_dist[u][p].first << "\n";
break;
}
p++;
}
}
for (int i=0;i<sz;i++) {
banned[V[i]]=false;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int _t = 1;
for (int i=1;i<=_t;i++) {
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... |