이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int mx=500000;
const int mx2=2e4+19;
typedef long long ll;
const int mod=998244353 ;
const int SQ=350;
const ll inf=1e9+10;
int n,m,q;
vector<int>adj[mx]; vector <pair <int, int>>f[mx];int vis[mx];int vis2[mx];int cur=1;int dp[mx];
vector< pair<int,int>> merge(vector< pair < int ,int > > &l, vector< pair < int,int > >&r){
int left=0; int right=0; int lsize=l.size(); int rsize=r.size();
vector<pair<int,int>>ret;
while(ret.size()<SQ&&(left<lsize||right<rsize)){
pair<int,int>ok;
if(left==lsize){
ok=r[right];
ok.first++;
right++;
}else if(right==rsize){
ok=l[left];
left++;
}else if(l[left].first>r[right].first+1){
ok=l[left];
left++;
}else{
ok=r[right];
right++;
ok.first++;
}
if(vis[ok.second]==cur){continue;}
vis[ok.second]=cur;
ret.push_back(ok);
}
return ret;
}
int main(){
cin>>n>>m>>q;
for(int i=0;i<m;i++){
int x,y;cin>>x>>y;
adj[y].push_back(x);
}
for(int i=1;i<=n;i++){
f[i].push_back({0,i});
for(auto&j:adj[i]){
f[i] = merge(f[i], f[j]);
cur++;
}
}
/*
cout<<"TEST \n";
for(auto it:f[4]){
cout<<it.second<<" "<<it.first<<endl;
}
cout<<endl;
*/
while(q--){
int idx,y;
cin>>idx>>y;
int arr[y];
for(int j=0;j<y;j++){
cin>>arr[j];
vis2[arr[j]]=1;
}
if(y<SQ){
int ans=-1;
for(auto it:f[idx]){
if(vis2[it.second]){continue;}
ans=max(ans,it.first);
break;
}
cout<<ans<<"\n";
}else{
int ans=-1;
vector<int>dis(idx+1,-1);
dis[idx]=0;
for(int j=idx;j>=1;j--){
for(auto it:adj[j]){
dis[it]=max(dis[it],dis[j]+1);
}
if(vis2[j]){}else{ ans=max(ans,dis[j]); }
}
cout<<ans<<"\n";
}
for(int j=0;j<y;j++){
vis2[arr[j]]=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... |