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>
// #define int long long
#define F first
#define S second
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << endl, exit(0);
#define mp make_pair
#define pb push_back
#define endl "\n"
using namespace std;
typedef long long ll;
const int MAXN = (int)1e6 + 7;
const int MOD = 999999893;
const int INF = (int)1e9 + 7;
const int SQ = 600;
int n, m, t, flag, u, v, w, k, tmp, tmp2, tmp3, tmp4, tmp5, tmp6, ans, q, ans2;
int arr[MAXN], cnt2[MAXN], love[MAXN];
bool hate[MAXN], op[MAXN];
vector<pii> vec[MAXN]; vector<int> adj[MAXN]; vector<int> tvec;
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> q;
for (int i=0; i<m; i++) {
cin >> u >> v;
adj[v].pb(u);
}
fill(arr, arr+n+7, -1);
for (int i=1; i<=n; i++) {
vec[i].pb(mp(0, i)); tvec.clear();
for (int u:adj[i]) {
for (auto cur:vec[u]) {
if (arr[cur.S] == -1) {
arr[cur.S] = cur.F;
tvec.pb(cur.S);
} else if (cur.F > arr[cur.S]) {
arr[cur.S] = cur.F;
}
}
}
for (int u:tvec) vec[i].pb(mp(arr[u]+1, u)), arr[u] = -1;
sort(all(vec[i]), greater<pii>());
while (vec[i].size() > SQ) vec[i].pop_back();
// cout << "#" << i << endl;
// for (auto cur:vec[i]) cout << "@" << cur.F << " " << cur.S << endl;
}
while (q--) {
cin >> v >> w;
tvec.clear();
for (int i=0; i<w; i++) {
cin >> u;
tvec.pb(u); op[u] = 1;
}
// cout << "!";
if (w < SQ) {
ans = -1;
for (auto cur:vec[v]) {
if (!op[cur.S]) {
ans = cur.F;
break;
}
}
cout << ans << endl;
} else {
for (int i=1; i<=v; i++) {
love[i] = (op[i]? -1 : 0);
for (int u:adj[i]) if (love[u] != -1 && love[u]+1 > love[i]) love[i] = love[u]+1;
}
cout << love[v] << endl;
}
for (int i=0; i<w; i++) op[tvec[i]] = 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... |