Submission #233956

#	Time	Username	Problem	Language	Result	Execution time	Memory
233956		kshitij_sodani	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2084 ms	6908 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
int n,m,q,aa,bb;
int vis[100001];
vector<int> adj[100001];
int x;
const int ss=316;
int dp[100001];
int calc(int ind){
	for(int i=0;i<ind+1;i++){
		dp[i]=0;
		if(vis[i]){
			dp[i]=-1;
		}
		for(auto j:adj[i]){
			if(dp[j]!=-1){
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
	}
	return dp[ind];
}
pair<int,int> dist[100001][ss];
int ind[100001];
int pre(){
	for(int i=0;i<n;i++){
		priority_queue<pair<int,int>> sso;
		for(auto j:adj[i]){
			for(int k=0;k<ind[j];k++){
				sso.push(dist[j][k]);
			
			}
		}
		int co=0;
		while(co<ss and sso.size()){
			pair<int,int> tt=sso.top();
			sso.pop();
			if(vis[tt.b]){
				continue;
			}
			vis[tt.b]=1;
			dist[i][co]={tt.a+1,tt.b};
	//		cout<<i<<","<<tt.a+1<<","<<tt.b<<endl;
			co+=1;
		}
		for(int j=0;j<co;j++){
			vis[dist[i][j].b]=0;
		}
		if(co<ss){
			dist[i][co]={0,i};
	//		cout<<i<<","<<0<<" "<<i<<endl;
			co+=1;
		}
		ind[i]=co;
	//	cout<<i<<"  "<<co<<endl;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m>>q;
	for(int i=0;i<n;i++){
		vis[i]=0;
	}
	for(int i=0;i<m;i++){
		cin>>aa>>bb;
		adj[bb-1].pb(aa-1);
	}
	pre();
	int indd,nn;
	for(int ii=0;ii<q;ii++){
		cin>>indd>>nn;
		indd-=1;
		vector<int> cur;
		int co=0;
		for(int j=0;j<nn;j++){
			cin>>x;
			x-=1;
		//	if(adj[x].size()==0){
				vis[x]=1;
				cur.pb(x);
				co+=1;
		//	}
		}
		if(co>=ss){
			cout<<calc(indd)<<endl;
		}
		else{
			int st=0;
			for(int i=0;i<ind[indd];i++){
				if(vis[dist[indd][i].b]){
					continue;
				}
				st=1;
				cout<<dist[indd][i].a<<endl;
				break;
			}
			if(st==0){
				cout<<-1<<endl;
			}
		}
		for(auto j:cur){
			vis[j]=0;
		}
	}



	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int pre()':
bitaro.cpp:62:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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