이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const ll mod=1e9+7;
const int c=300;
using namespace std;
int n,m,q,x,y,i,j,nr,f[nmax],d[nmax],v[nmax],id[nmax],a[nmax],t;
vector<pair<int,int> >vc[nmax];
vector<int>g[nmax],cl;
pair<int,int>mx;
int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
cin>>n>>m>>q;
while(m--)
{
cin>>x>>y;
g[y].pb(x);
}
for(i=1;i<=n;i++)
{
for(j=0;j<(int)g[i].size();j++)
{
x=g[i][j];
f[i]=max(f[i],f[x]+1);
}
d[i]=f[i];
}
for(i=1;i<=n;i++)
{
for(j=0;j<(int)g[i].size();j++)id[g[i][j]]=0;
nr=(int)g[i].size();
for(t=0;t<c;t++)
{
mx=mkp(0,0);
for(j=0;j<(int)g[i].size();j++)
{
x=g[i][j];
if(id[x]==(int)vc[x].size())continue;
while(id[x]<(int)vc[x].size() && v[vc[x][id[x]].sc])id[x]++;
if(id[x]<(int)vc[x].size())mx=max(mx,vc[x][id[x]]);
else nr--;
}
if(mx.sc)
{
vc[i].pb(mkp(mx.fr+1,mx.sc));
v[mx.sc]=1;
cl.pb(mx.sc);
}
else break;
//if(!nr)break;
}
if((int)vc[i].size()<c)vc[i].pb(mkp(0,i));
for(j=0;j<(int)cl.size();j++)v[cl[j]]=0;
cl.clear();
}
while(q--)
{
cin>>x>>nr;
for(i=1;i<=nr;i++)
{
cin>>a[i];
v[a[i]]=1;
}
if(nr>=c)
{
for(i=a[1];i<=x;i++)
{
if(v[i])d[i]=-1;
else d[i]=0;
for(j=0;j<(int)g[i].size();j++)
{
y=g[i][j];
if(d[y]==-1)continue;
d[i]=max(d[i],d[y]+1);
}
}
cout<<d[x]<<'\n';
for(i=a[1];i<=x;i++)d[i]=f[i];
}
else
{
mx=mkp(-1,-1);
for(i=0;i<(int)vc[x].size();i++)
{
if(!v[vc[x][i].sc])
{
mx=vc[x][i];
break;
}
}
cout<<mx.fr<<'\n';
}
for(i=1;i<=nr;i++)v[a[i]]=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... |