Submission #94280

#	Time	Username	Problem	Language	Result	Execution time	Memory
94280		autumn_eel	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2054 ms	30368 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];
set<P>dp[200000];
unordered_map<int,int>mp[200000];

int dp2[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[s].push_back(t);
	}
	rep(i,n)dp[i].insert(P(0,i));
	rep(i,n){
		for(auto&p:dp[i]){
			for(int u:E[i]){
				int&d=mp[u][p.second];
				if(d<=p.first){
					dp[u].erase(P(d,p.second));
					d=p.first+1;
					dp[u].insert(P(d,p.second));
				}
				while(dp[u].size()>B)dp[u].erase(dp[u].begin());
			}
		}
	}
	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){
			sort(v.begin(),v.end());
			for(auto it=dp[t].rbegin();it!=dp[t].rend();it++){
				if(!binary_search(v.begin(),v.end(),it->second)){
					printf("%d\n",it->first);
					goto g;
				}
			}
			puts("-1");
			g:;
		}
		else{
			fill(dp2,dp2+n,0);
			for(int i:v)dp2[i]=-INF;
			rep(i,n){
				for(int u:E[i]){
					dp2[u]=max(dp2[u],dp2[i]+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:36: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:39: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: 0 / 7
• Subtask 3: 0 / 86