# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
983989 | Amaarsaa | Bitaro’s Party (JOI18_bitaro) | C++14 | 0 ms | 0 KiB |
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 = int ;
using pll = pair < ll, ll >;
ll used[100004], cant[100004];
vector < ll > adj[100004], radj[100004];
vector < pll > good[100003];
int main() {
// freopen("moocast.in", "r", stdin);
// freopen("moocast.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);
ll n, m, q, i, ans, x, y, I, I1, i1, t;
cin >> n >> m >> q;
for (i = 1; i <= m; i ++) {
cin >> x >> y;
adj[x].push_back(y);
radj[y].push_back(x);
}
for (i = 1; i <= m; i ++) {
vector < pll > v;
for ( ll I : radj[i]) {
i1 = I1 = 0;
good[i].push_back({0ll, i});
used[0] = 1;
while ( i1 < good[i].size() || I1 < good[I].size()) {
if (I1 == good[I].size() || (i1 != good[i].size() && good[i][i1].first > good[I][I1].first + 1)) {
v.push_back(good[i][i1]);
i1 ++;
used[v.back().second] = 1;
}
else {
v.push_back(good[I][I1]);
v.back().first ++;
I1 ++;
used[v.back().second] = 1;
}
while (i1 < good[i].size() && used[good[i][i1].second]) i1 ++;
while (I1 < good[I].size() && used[good[I][I1].second]) I1 ++;
}
good[i].pop_back();
for ( pll &A : good[i]) used[A.second] = 0;
swap(good[i], v);
}
}
while ( q --) {
cin >> t >> m;
ll c[m + 2];
for ( i = 1; i <= m; i ++) {
cin >> c[i];
cant[c[i]] = 1;
}
ans = -1;
if ( m <= 100) {
for ( pll &A : good[t]) {
if (!cant[A.second]) {
ans = A.first;
break;
}
}
if (!cant[t]) ans = max(ans, int(0));
}
else {
ll dp[n + 2];
for (i = 1; i <= n; i ++) dp[i] = -1;
for (i = 1; i <= n; i ++) {
if ( cant[i] == 1 && dp[i] == -1) continue;
dp[i] = max(0ll, dp[i]);
for ( int I : adj[i]) {
dp[I] = max(dp[I], dp[i] + 1);
}
}
ans = dp[t];
}
for (i =1 ; i <= m; i ++) cant[c[i]] = 0;
cout << ans << endl;
}
/*
for (i = 1; i <= n; i ++) {
cout << i << " " << good[i].size() << endl;
for (pll X : good[i]) {
cout << X.first << " " << X.second << endl;
}
cout << endl;
}
*/
}