Submission #94287

#	Time	Username	Problem	Language	Result	Execution time	Memory
94287		autumn_eel	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1602 ms	72312 KiB

bitaro

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int>P;

#define B 40

vector<int>E[200000];
vector<P>dp[200000];
P mp[200000];
int dp2[200000];
bool b[200000];

int main(){
	int n,m,q;cin>>n>>m>>q;
	rep(i,m){
		int s,t;scanf("%d%d",&s,&t);s--;t--;
		E[t].push_back(s);
	}
	rep(i,n)dp[i].push_back(P(0,i));
	rep(i,n)mp[i]=P(-INF,-1);
	rep(i,n){
		for(int u:E[i]){
			for(auto&p:dp[u]){
				if(mp[p.second].second!=i){
					mp[p.second]=P(p.first+1,i);
				}
				else{
					mp[p.second]=max(mp[p.second],P(p.first+1,i));
				}
				b[p.second]=false;
			}
		}
		for(int u:E[i]){
			for(auto&p:dp[u]){
				if(!b[p.second]){
					dp[i].push_back(P(mp[p.second].first,p.second));
					b[p.second]=true;
				}
			}
		}
		sort(dp[i].begin(),dp[i].end(),greater<>());
		while(dp[i].size()>B)dp[i].pop_back();
	}
	memset(b,0,sizeof(b));
	rep(i,q){
		int t,y;scanf("%d%d",&t,&y);t--;
		vector<int>v;
		rep(j,y){
			int c;scanf("%d",&c);c--;
			v.push_back(c);
		}
		if(y<B){
			for(int i:v)b[i]=true;
			for(auto&p:dp[t]){
				if(!b[p.second]){
					printf("%d\n",p.first);
					goto g;
				}
			}
			puts("-1");
			g:;
			for(int i:v)b[i]=false;
		}
		else{
			fill(dp2,dp2+t+1,0);
			for(int i:v)dp2[i]=-INF;
			rep(i,t+1){
				for(int u:E[i]){
					dp2[i]=max(dp2[i],dp2[u]+1);
				}
			}
			printf("%d\n",dp2[t]<0?-1:dp2[t]);
		}
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:18:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s,t;scanf("%d%d",&s,&t);s--;t--;
           ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:48:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int t,y;scanf("%d%d",&t,&y);t--;
           ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:51:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int c;scanf("%d",&c);c--;
          ~~~~~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86