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;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int oo = 1e9;
const int B = 211;
const int N = 2e5+10;
bool seen[N];
int dp[N];
int main(){
cin.tie(NULL),cin.sync_with_stdio(false);
int n,m,q; cin >> n >> m >> q;
vvi rev(n);
rep(i,0,m){
int s,e; cin >> s >> e;
s--,e--;
rev[e].push_back(s);
}
vector<vector<array<int,2>>> prec(n);
for(auto& v : prec) v.reserve(B+2);
rep(i,0,n){
vector<array<int,2>> cur = {{-1,i}};
for (auto to : rev[i]) cur.insert(end(cur),all(prec[to]));
sort(all(cur));
reverse(all(cur));
for(int j = 0; j < sz(cur) and sz(prec[i]) < B+2; ++j) {
auto [v,at] = cur[j];
if (!seen[at]){
seen[at] = 1;
prec[i].push_back({v+1,at});
}
}
for(auto [v,at] : prec[i]) seen[at] = 0;
}
while(q--){
int t,y; cin >> t >> y;
t--;
vector<int> c(y);
rep(i,0,y) cin >> c[i], c[i]--;
if (y>B){
fill(dp,dp+t+1,0);
for(auto at : c) dp[at] = -oo;
for(int i = 0; i <= t; ++i){
for(auto to : rev[i]) dp[i] = max(dp[i],dp[to]+1);
}
if (dp[t]<0) cout << "-1\n";
else cout << dp[t] << '\n';
}else{
bool done = 0;
for(auto [v, at] : prec[t])
if (!binary_search(all(c),at)){
cout << v << '\n';
done = 1;
break;
}if (!done){
cout << "-1\n";
}
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |