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>
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 1e5+10,mod = 998244353,inf = 1e9+10,sq = 500;
inline int mkay(int a,int b){
if (a+b >= mod) return a+b-mod;
if (a+b < 0) return a+b+mod;
return a+b;
}
inline int poww(int a,int k){
if (k < 0) return 0;
int z = 1;
while (k){
if (k&1) z = 1ll*z*a%mod;
a = 1ll*a*a%mod;
k /= 2;
}
return z;
}
vector<int> out[N],in[N];
int d[N];
bool bad[N];
pll mx[N][sq];
bool vis[N];
inline void mg(int u,int v){
int po = 0,po2 = 0;
vector<pll> tmp;
int sz = 0;
while(sz < sq && (po < sq || po2 < sq)){
if (po == sq || mx[u][po].Y == -1){
int x = mx[v][po2].Y;
if (x == -1){
break;
}
if (vis[x]){
po2++;
continue;
}
sz++;
vis[x] = 1;
tmp.pb({mx[v][po2].X+1,x});
continue;
}
if (po2 == sq || mx[v][po2].Y == -1){
int x = mx[u][po].Y;
if (x == -1){
break;
}
if (vis[x]){
po++;
continue;
}
sz++;
vis[x] = 1;
tmp.pb(mx[u][po]);
continue;
}
int x = mx[u][po].Y;
if (vis[x]){
po++;
continue;
}
int y = mx[v][po2].Y;
if (vis[y]){
po2++;
continue;
}
sz++;
if (mx[u][po].X >= mx[v][po2].X+1){
vis[x] = 1;
tmp.pb(mx[u][po]);
po++;
}
else{
vis[y] = 1;
tmp.pb({mx[v][po2].X+1,y});
po2++;
}
}
rep(i,0,sz) mx[u][i] = tmp[i];
rep(i,sz,sq) mx[u][i] = {-inf,-1};
rep(i,0,sq){
int x = mx[v][i].Y,y = mx[u][i].Y;
if (x >= 0) vis[x] = 0;
if (y >= 0) vis[y] = 0;
}
}
int main(){
ios :: sync_with_stdio(0); cin.tie(0);
int n,m,q;
cin >> n >> m >> q;
rep(i,0,m){
int u,v;
cin >> u >> v;
out[u].pb(v);
in[v].pb(u);
}
rep(i,1,n+1){
mx[i][0] = {0,i};
rep(j,1,sq) mx[i][j] = {-inf,-1};
}
rep (i,2,n+1){
for (int j : in[i]){
mg(i,j);
}
}
while (q--){
int u,t;
vector<int> ve;
cin >> u >> t;
ve.resize(t);
rep(i,0,t){
cin >> ve[i];
bad[ve[i]] = 1;
}
if (t < sq){
rep(i,0,sq){
if (mx[u][i].Y == -1){
cout << -1 << endl;
break;
}
if (!bad[mx[u][i].Y]){
cout << mx[u][i].X << endl;
break;
}
}
for (int x : ve) bad[x] = 0;
continue;
}
int mx = -1;
memset(d,128,sizeof d);
d[u] = 0;
repr(i,u,1){
if (!bad[i]) mx = max(mx,d[i]);
for (int j : in[i]){
d[j] = max(d[j],d[i]+1);
}
}
for (int x : ve) bad[x] = 0;
cout << mx << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |