# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
774607 | DobromirAngelov | Bitaro’s Party (JOI18_bitaro) | C++14 | 6 ms | 5460 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
using namespace std;
const int MAXN=1e5+5;
const int B=300;
int n,m,q;
pair<int,int> maxd[MAXN][B+5];
vector<int> adj[MAXN];
int dp[MAXN];
int c[MAXN];
bool used[MAXN];
int calc_dp(int v)
{
memset(dp,0,sizeof(dp));
for(int i=v-1;i>=1;i--)
{
for(int j=0;j<adj[i].size();j++)
{
if(adj[i][j]>v) continue;
dp[i]=max(dp[i], dp[adj[i][j]]+1);
}
}
int ans=-1;
for(int i=v;i>=1;i--)
{
if(!used[i]) ans=max(ans, dp[i]);
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m>>q;
for(int i=0;i<m;i++)
{
int u,v;
cin>>u>>v;
adj[u].push_back(v);
}
for(int i=0;i<=n;i++)
{
for(int j=1;j<B;j++) maxd[i][j].fi=-1;
}
for(int i=0;i<=n;i++) maxd[i][0].fi=0, maxd[i][0].se=i;
for(int v=1;v<=n;v++)
{
for(int j=0;j<adj[v].size();j++)
{
int to=adj[v][j];
int ptr1=0;
int ptr2=0;
vector<pair<int,int> > tmp;
for(;;)
{
if(tmp.size()>=B) break;
if(maxd[v][ptr1].fi!=-1 && maxd[v][ptr1].fi+1>maxd[to][ptr2].fi)
{
tmp.push_back({maxd[v][ptr1].fi+1, maxd[v][ptr1++].se});
}
else if(maxd[to][ptr2].fi!=-1)
{
tmp.push_back({maxd[to][ptr2].fi, maxd[to][ptr2++].se});
}
else break;
}
for(int i=0;i<tmp.size();i++) maxd[to][i]=tmp[i];
}
}
for(int i=0;i<q;i++)
{
int v,br;
cin>>v>>br;
for(int j=0;j<br;j++)
{
cin>>c[j];
used[c[j]]=1;
}
if(br<=B)
{
bool fl=0;
for(int j=0;j<B;j++)
{
if(maxd[v][j].fi<0) break;
if(!used[maxd[v][j].se])
{
cout<<maxd[v][j].fi<<endl;
fl=1;
break;
}
}
if(!fl) cout<<-1<<endl;
}
else
{
int ans=calc_dp(v);
cout<<ans<<endl;
}
for(int j=0;j<br;j++) used[c[j]]=0;
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |