| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 567283 | shrimb | Bitaro’s Party (JOI18_bitaro) | C++17 | 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.
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")
#include"bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991
const int maxn = 200001;
const int sq = 2000;
vector<int> adj[maxn], radj[maxn];
int n, m, q;
pair<int,int> dp[maxn][sq];
int dp2[maxn];
int c[maxn];
bitset<maxn> rem;
signed main () {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
for (int i = 0 ; i < m ; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
radj[b].push_back(a);
}
for (int i = 1 ; i <= n ; i++) {
for (int j = 0 ; j < sq ; j++) dp[i][j] = {-1e9,-1};
dp[i][0] = {0, i};
}
for (int i = 1 ; i <= n ; i++) {
vector<pair<int,int>> v;
for (auto k : dp[i]) {
if (k.second == -1) break;
v.push_back(k);
}
for (int j : radj[i]) {
for (auto k : dp[j]) {
if (k.second == -1) break;
v.push_back({k.first + 1, k.second});
}
}
sort(v.begin(), v.end(), greater<pair<int,int>>());
// cerr << v.size() << endl;
for (int j = 0 ; j < min(sq, (int)v.size()) ; j++) dp[i][j] = v[j];
// cerr << "here\n";
}
for (int i = 0 ; i < q ; i++) {
int t, y;
cin >> t >> y;
for (int j = 0 ; j < y ; j++) cin >> c[j], rem[c[j]] = 1;
if (y < sq - 1) {
for (int j = 0 ; j < sq ; j++) {
if (dp[t][j].second == -1) break;
if (!rem[dp[t][j].second]) {
cout << dp[t][j].first << endl;
goto good;
}
}
cout << -1 << endl;
good:;
}
// else {
// for (int j = 1 ; j <= t ; j++) {
// dp2[j] = (rem[j] ? -1e9 : 0);
// for (int k : radj[j]) dp2[j] = max(dp2[j], dp2[k] + 1);
// }
// if (dp2[t] < 0) cout << -1 << endl;
// else cout << dp2[t] << endl;
// }
for (int j = 0 ; j < y ; j++) rem[c[j]] = 0;
}
}