| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 944010 | RadicaI | 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.
#include <bits/stdc++.h>
#define pi pair<int,int>
#define pb push_back
#define V vector
#define vi V<int>
#define mi map<int,int>
#define MOD 1000000007
#define MOD2 998244353
#define mp make_pair
#define ins insert
#define qi queue<int>
#define pqi priority_queue<int>
#define si set<int>
#define v2i V<vi>
#define v3i V<v2i>
#define v4i V<v3i>
#define v5i V<v4i>
#define INF 1e18
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl "\n"
#define lb lower_bound
#define ub upper_bound
#define print(x) cout << x<<" ";
#define vpi V<pi>
#define Y cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define msi multiset<int>
#define F first
#define S second
#define ld long double
#define RE return;
#define IMP cout<<-1<<endl;return;
using namespace std;
template <typename T>
std::istream& operator>>(std::istream& in, std::vector<T>& vec) {
for (T& x : vec) {
in >> x;
}
return in;
}
const int block = 350;
signed main(){
fastio;
int n,m,q; cin>>n>>m>>q;
v2i adj(n);
for(int i=0; i<m; i++){
int s,e; cin>>s>>e; s--;e--;
adj[e].pb(s);
}
V<set<pi>> mx(n);
for(int i=0; i<n; i++){
mx[i].ins({0,i});
map<int,si> jhxt;
for(auto &x: adj[i]){
for(auto &y: mx[x]){
jhxt[y.S].ins(y.F+1);
}
}
for(auto &x: jhxt){
mx[i].ins({*x.S.rbegin(), x.F});
if(sz(mx[i])>block) mx[i].erase(mx[i].begin());
}
}
vi store(n, q+1);
while(q--){
int t,y; cin >> t>>y;
t--;
for(int i=0; i<y; i++){int x; cin >> x; store[x-1]=q;}
if(y>=block){
vi dp(t+1,-1);
for(int i=0; i<=t; i++){
if(store[i]!=q)dp[i]=max(dp[i],0ll);
for(auto &x: adj[i]){
if(dp[x]!=-1)dp[i] = max(dp[x]+1, dp[i]);
}
}
cout << dp[t]<<endl;
}else{
int ans = -1;
for(auto &x: mx[t])if(store[x.S]!=q) ans = x.F;
cout<<ans<<endl;
}
}
}