Submission #492728

#	Time	Username	Problem	Language	Result	Execution time	Memory
492728		Md_yz	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	1793 ms	198904 KiB

bitaro

// elahi shokrt
 
// resad adami be jaee ke be joz khoda nabinad 	
		//bengar ke ta che had ast makan adamiat!
		
#include<bits/stdc++.h>
using namespace std ;
#define pb push_back
#define all(v) v.begin(),v.end()
#define M '\n'
#define f first 
#define s second 
typedef long long int lli ; 
typedef pair<lli,lli>  pll; 
const lli mma=1e5+10;
const lli mod = 1e9+7 ; 
const lli sq = 110 ; 
const lli inf = 1e9 ; 
 
vector<lli> g[mma]; 
 
lli n , m , q ; 
pll dp[mma][sq+12]; 
bool seen[mma]; 
bool seen1[mma]; 
void benazaretbehtare(lli u , lli i ){
	vector<pll> v;
	for(int j = 0 ; j  <sq ; j++){
	   v.pb(dp[i][j]); 
	   v.pb(pll(dp[u][j].f+1,dp[u][j].s)); 
	}
	
	sort(all(v)); 
	reverse(all(v));
	lli j = 0; 
		
	for(pll p : v ){
		
		if(p.s!=-inf && seen1[p.s]){
			
		}
		else{
			dp[i][j] = p ; 
			if(p.s!=-inf)
		      seen1[p.s] = 1; 
		    j++; 
		    if(j==sq)
		            break; 	
		}
		
	}
		
	for(int j  = 0 ; j < sq ; j++){
		      if(dp[i][j].s!=-inf)
		            seen1[dp[i][j].s] = 0 ;   
		      
	}
	return ; 
	
}
int main (){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	cin >> n >> m >> q; 
	for(int i = 0; i < m ; i++){
		lli u , v; 
		cin >> u >> v ; u-- ; v--; 
		g[v].pb(u); 
		
	}
	for(int i = 0; i < mma ; i++){
		for(int j = 0; j  < sq ; j++){
			
			dp[i][j] = pll(-inf,-inf); 
		}
		
	}
	
	for(int i = 0; i  < n ; i++){
		
		pll tmp ;
		tmp.f = 0 ; 
		tmp.s = i ; 
		dp[i][0] = tmp ; 
	
	
		
		for(int u : g[i]){
		      benazaretbehtare(u,i);
		}
			
	}
	
//	return 0 ; 
	
	while(q--){
		lli t , y; 
		cin >> t >> y ; 
		if(y>=sq){
			
			t--; 
			lli dnp[mma]; 
			fill(dnp,dnp+n,0); 
			for(int j = 0 ; j < y ; j++){
				lli v ; 
				cin >> v ; v--; 
				dnp[v] = -inf ; 
				
			}
			
			for(int j = 0 ; j  < n ; j++){
				for(int u : g[j]){
					dnp[j] = max(dnp[u]+1,dnp[j]); 
				}
				//cout<<j<<" "<<dnp[j]<<endl ;
			}
			
			cout<<max(1ll * (-1) ,dnp[t])<<M; 
			
			
		}
		else{
			
			t--; 
			vector<lli> v ;
			for(int i = 0; i < y ; i++){
				
				lli u ; 
				cin >> u ; u-- ; 
				v.pb(u);
				seen[u] = 1 ; 
				
			}
			
			for(int j = 0 ; j  < sq ; j++){
				if(dp[t][j].second==-inf){
					cout<<-1<<M; 
					break ; 
				}
				else if(!seen[dp[t][j].second]){
					cout<<dp[t][j].first<<M; 
					break ;
				}
				
			}
			for(int u : v ){
				seen[u] = 1; 
			}
		}
		
	}
	return 0 ; 
	
}

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