제출 #492710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
492710		Md_yz	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	2 ms	3404 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 = 200 ; 
const lli inf = 1e9 ; 

vector<lli> g[mma]; 
 
lli n , m , q ; 
pll dp[mma][sq]; 
bool seen[mma]; 
bool seen1[mma]; 
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 < n ; i++){
		for(int j = 0 ; j < sq ; j++){
			dp[i][j] = pll(-inf,-inf); 
		}
	}
	//return 0 ; 
	for(int i = 0; i  < n ; i++){
		pll tmp ;
		tmp.f = 0 ; 
		tmp.s = i ; 
		dp[0][i] = tmp ; 
		// u va i 
		vector<pll> v; 
		for(int u : g[i]){
		      
		      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(j==sq){
		            break ;
		      }
		      if(p.s!=-inf && seen1[p.s]==0){
		          seen1[p.s] = 1 ;
		          dp[i][j] = p ; 
		          j++; 
		           
		      }
		}
		for(int j  = 0 ; j < sq ; j++){
		      if(dp[i][j].second!=-inf)
		            seen1[dp[i][j].s] = 0 ; 
		      else
		            break;
		}
		
	}
	
	//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] = 0 ; 
				
			}
			
			for(int j = 0 ; j  < sq ; j++){
				if(dp[t][j].second==-inf){
					cout<<-1<<endl; 
					break ; 
				}
				else if(!seen[dp[t][j].second]){
					cout<<dp[t][j].first<<endl; 
					break ;
				}
				
			}
			for(int u : v ){
				seen[u] = 1; 
			}
		}
		
	}
	return 0 ; 
	
}

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