Submission #1067029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067029		Rawlat_vanak	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1358 ms	215388 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define f first
#define s second
#define pii pair<int,int>
#define pb push_back

vector<vector<int>> graph;
const int block=100;

int32_t main(){
	speedIO;
	int t,n,m,q,k;

	//cin>>t;
	//t=1;
	//while(t--){
		//string s;		
		cin>>n>>m>>q;
		graph.resize(n+1);
		for(int i=0;i<m;i++){
			int s,e;
			cin>>s>>e;
			graph[e].pb(s);
		}
		
		vector<vector<pii>> distance(n+1);
		
		
		distance[1].pb({0,1});
		for(int i=2;i<=n;i++){
			//distance[i].pb({0,i});
			vector<bool> visited(n+1,false);
			vector<pii> tmp;
			tmp.pb({0,i});
			//visited[i]=true;
			for(int j:graph[i]){
				for(pii d: distance[j]){
					
					tmp.pb({d.f+1,d.s});
				}
			}

			sort(tmp.rbegin(),tmp.rend());

	
			int sz=0,idx=0;
			while(sz<block and idx<tmp.size()){
				if(visited[tmp[idx].s]){
					//cout<<"sobsob "<<i<<' '<<tmp[idx].s<<'\n';
					idx++;
				}else{
					visited[tmp[idx].s]=true;
					distance[i].pb(tmp[idx]);
					sz++;idx++;
				}
			}
			
		}
		/*for(int i=1;i<=n;i++){
			for(pii j:distance[i]){
				cout<<j.f<<' ';
			}
			cout<<'\n';
		}*/
		while(q--){
			int t,y;
			cin>>t>>y;
			vector<bool> blocked(n+1,false);
			for(int i=0;i<y;i++){
				int buh;
				cin>>buh;
				blocked[buh]=true;
			}

			if(y<block){
				bool done=false;
				for(pii i :distance[t]){
					if(!blocked[i.s]){
						done=true;
						cout<<i.f<<'\n';
						break;
					}
				}
				if(!done){
					cout<<-1<<'\n';
				}
			}else{
			     //cout<<"hi"<<'\n';
				vector<int> dp(n+1,-1);
				dp[t]=0;
				for(int i=t;i>0;i--){
					for(int j:graph[i]){
					     if(dp[i]!=-1){
						     dp[j]=max(dp[j],dp[i]+1);
					     }
					}
				}
				
				int ans=-1;
				for(int i=1;i<=t;i++){
					if(!blocked[i]){
						ans=max(ans,dp[i]);
					}
				}
				cout<<ans<<'\n';

			}

			
		}


		
		

		
		


	//}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int32_t main()':
bitaro.cpp:51:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |    while(sz<block and idx<tmp.size()){
      |                       ~~~^~~~~~~~~~~
bitaro.cpp:16:6: warning: unused variable 't' [-Wunused-variable]
   16 |  int t,n,m,q,k;
      |      ^
bitaro.cpp:16:14: warning: unused variable 'k' [-Wunused-variable]
   16 |  int t,n,m,q,k;
      |              ^

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