이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Code by Parsa Eslami
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define err(x) cerr<#x<<" : "<<x<<'\n'
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define pb push_back
#define bit(i,j) ((j>>i)&1)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define dmid int mid=(r+l)/2
#define lc 2*id
#define rc 2*id+1
using namespace std;
const int N=1e5+4;
const int SQ=340;
vector<int> adj[N];
vector<pii> vc[N];
int ind[N];
int dp[N];
bool mark[N];
int32_t main(){
iostream::sync_with_stdio(0); cin.tie(0);
int n,m,q; cin>>n>>m>>q;
FOR(i,1,m){
int v,u; cin>>v>>u;
adj[u].pb(v);
}
FOR(i,1,n){
vector<pii> vc0;
vc[i].pb({-1,i});
while(SZ(vc0)<=SQ){
pair<pii,int> mx={{-2,-1},0};
if(ind[i]<SZ(vc[i])){
pair<pii,int> O={vc[i][ind[i]],i};
maxm(mx,O);
}
for(int u:adj[i]) if(ind[u]<SZ(vc[u])){
pair<pii,int> O={vc[u][ind[u]],u};
maxm(mx,O);
}
mx.F.F++;
if(mx.F.F==-1) break;
ind[mx.S]++;
vc0.pb(mx.F);
}
vc[i]=vc0;
ind[i]=0;
for(int u:adj[i]) ind[u]=0;
}
FOR(__,1,q){
int v; cin>>v;
vector<int> bad; int w; cin>>w;
FOR(_,1,w){
int x0; cin>>x0; bad.pb(x0);
mark[x0]=1;
}
int ans=-1;
if(w>=SQ){
FOR(i,1,v-1) dp[i]=-1;
dp[v]=0;
FORR(i,v,1) if(dp[i]!=-1)
for(int u:adj[i]) maxm(dp[u],dp[i]+1);
FOR(i,1,v) if(!mark[i]) maxm(ans,dp[i]);
}else{
for(pii x0:vc[v]) if(!mark[x0.S]) maxm(ans,x0.F);
}
cout<<ans<<'\n';
for(int w0:bad) mark[w0]=0;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |