Submission #354383

#	Time	Username	Problem	Language	Result	Execution time	Memory
354383		RohamIzadidoost	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1811 ms	120812 KiB

bitaro

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)(x).size()
#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 1000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int sq = 128 ; 
int n , m , q , dp[maxn]  ,z , mark[maxn] , cnt , c[maxn] , ans ; 
vec<int> out[maxn] , in[maxn];
vec<pii> adj[maxn]  , t ;  
int main()
{
	migmig ;
	vec<int> T(maxn) ; 
	cin>>n>>m>>q ; 
	for(int i = 1 ; i <= m ; i ++ ){
		int u , v ; 
		cin>>u>>v ; 
		if(u > v) swap(u , v) ; 
		out[u].pb(v) ; 
		in[v].pb(u) ; 
	}
/*	for(int i = 1 ; i <= n ; i++ ){
		for(auto u : in[i]){
			dp[i] = max(dp[i] , dp[u] + 1) ; 
		}
	//	adj[i].pb({0 , i}) ; 
	}*/
	for(int i = 1 ; i <= n ; i ++ ){
		for(auto u : in[i]){
			for(auto v : adj[u]){
				t.pb({v.X + 1 , v.Y}) ; 
			}
			/*z = sz(adj[i]) ; 
			for(auto u : adj[i]) cout<<u.X<<","<<u.Y << " " ; cout<<endl ; for(auto u : t) cout<<u.X <<"," << u.Y <<" " ; cout<<endl ; 
			merge(adj[i].begin() , adj[i].begin() + z , all(t) , T.begin() , greater<pii>()) ;
			t.clear() ; */
		}
		t.pb({0 , i}) ; 
		cnt = 0 ; 
		sort(all(t) , greater<pii>()) ; 
		for(auto u : t){
			if(!mark[u.Y]){
				adj[i].pb({u.X , u.Y}) ; cnt++ ; 
				mark[u.Y] = 1 ; 
			}
			if(cnt >= sq) break ;
		}
		t.clear() ; 
		for(auto u : adj[i]) mark[u.Y] = 0 ; 
	//	adj[i].resize( min( (int)sz(adj[i]) , sq) ) ; 
		/*cout<<i <<" : " ; 
		for(auto u : adj[i]) cout<<u.X <<","<<u.Y <<" "  ; 
		cout<<endl ; */
	}
	int v, k ; 
	while(q--){
		cin>>v>>k ; 
		for(int i= 0 ; i < k ; i ++ ){
			cin>>c[i] ; 
			mark[c[i]] = 1 ;
		}
		ans = -1 ; 
		if(k >= sq){
			for(int i = 1 ; i <= n ; i ++ ) dp[i] = -mod ; dp[v] = 0 ; 
		/*	for(int i = 1 ; i <= v ; i++ ){
				if(!mark[i]) dp[i] = 0 ;  
				for(auto u : in[i]){
					if(mark[u]) continue ; 
					dp[i] = max(dp[i] , dp[u] + 1) ; 
				}
			}
			if(dp[v] < 0 ) cout<<-1<<"\n" ; else cout<<dp[v] <<"\n" ; */
			for(int i = v ; i >= 1 ; i -- ){
				for(auto u : out[i]){
					dp[i] = max(dp[i] , dp[u] + 1) ;  
				}
				if(!mark[i]){
					ans = max(ans , dp[i]) ; 
				}
			}
			cout<<ans<<"\n" ; 
			for(int i = 0 ; i < k ; i ++ ) mark[c[i]] = 0 ; 
			continue ; 
		}
		for(auto u : adj[v]){
			if(!mark[u.Y]){
				ans = u.X ; 
				break ; 
			}
		}
		cout<<ans << "\n" ; 
		for(int i = 0 ; i < k ; i ++ ) mark[c[i]] = 0 ; 
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:80:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   80 |    for(int i = 1 ; i <= n ; i ++ ) dp[i] = -mod ; dp[v] = 0 ;
      |    ^~~
bitaro.cpp:80:51: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   80 |    for(int i = 1 ; i <= n ; i ++ ) dp[i] = -mod ; dp[v] = 0 ;
      |                                                   ^~

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