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 ll long long
const int nmax = 2e5 + 5, N = 3e5 + 5;
const ll oo = 1e18;
const int lg = 18, M = 4e3;
const int base = 2e5, mod = 1e9 + 7;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';cout << endl
using namespace std;
vector<int> adj[nmax];
vector<pii> gg[nmax];
int n, m, q;
int vis[nmax], c[nmax], dp[nmax];
int res[nmax], a[nmax];
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n >> m >> q;
for(int i = 1, u, v; i <= m; ++i){
cin >> u >> v;
adj[v].push_back(u);
}
int S = 100;
vector<pii> tmp;
for(int i = 1; i <= n; ++i){
gg[i].push_back({0, i});
for(auto v : adj[i]){
for(auto [d, x] : gg[v]){
tmp.push_back({d + 1, x});
res[x] = max(res[x], d + 1);
}
}
for(auto [d, x] : tmp){
if(res[x] == d){
gg[i].push_back({d, x});
res[x] = 0;
}
}
sort(gg[i].begin(), gg[i].end(), [](pii a, pii b){
return a.fi > b.fi;
});
while(gg[i].size() > S) gg[i].pop_back();
// for(auto [d, x] : gg[i]) cout << x << ' ';
// cout << endl;
}
while(q--){
int t, y;
cin >> t >> y;
if(y >= S){
for(int i = 1, x; i <= y; ++i) cin >> x, c[x] = 1;
for(int i = 1; i <= n; ++i) dp[i] = -n;
dp[t] = 0;
for(int i = t; i >= 1; --i){
for(auto v : adj[i]){
// cout << i << ' ' << v << endl;
dp[v] = max(dp[v], dp[i] + 1);
}
}
int ans = -1;
for(int i = 1; i <= t; ++i){
if(c[i]) continue;
// cout << i << ' ' << dp[i] << endl;
ans = max(ans, dp[i]);
}
for(int i = 1; i <= n; ++i)c[i] =dp[i]= 0;
cout << ans << endl;
}
else{
for(int i = 1,x; i <= y; ++i){
cin >> x, c[x] = 1;
a[i] = x;
}
bool ok = 0;
for(auto [d, x] : gg[t]){
if(c[x]) continue;
cout << d << endl;
ok = 1;
break;
}
for(int i = 1; i <= y; ++i) c[a[i]] = 0;
if(!ok) cout << -1 << endl;
}
}
}
/*
*/
Compilation message (stderr)
bitaro.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
21 | main(){
| ^~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:50:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
50 | while(gg[i].size() > S) gg[i].pop_back();
| ~~~~~~~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |