Submission #963351

#	Time	Username	Problem	Language	Result	Execution time	Memory
963351		TimAni	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1392 ms	419972 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int sq = 350,MAXN = 1e5+1;
bool take[MAXN],vis[MAXN];
int dp[MAXN];
vector<int>adj[MAXN],radj[MAXN];
vector<pii>good[MAXN];
//if y is >= k then run a naive dp,you will only encounter y>=K atmost n/k times so O(n * n/k)
//if y is < k then we only need to keep track of the k longest paths ending at each node,can do in O(m * k)
int main()
{
	owo
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=0;i<m;i++){
		int v,u;
		cin>>v>>u;
		adj[v].pb(u);
		radj[u].pb(v);
	}
	//good[i] stores the sq longest paths to i
	for(int i=1;i<=n;i++){
		for(int x:radj[i]){
			vector<pii>fin;
			good[x].pb({0,x});
			//duplicates are dangerous
			//remove duplicates while doing merge sort
			int a = 0,b=0;
			int sa = sz(good[x]);
			int sb = sz(good[i]);
			while(sz(fin)<sq  && (a<sa || b < sb)){
				if(b == sb ||  (a!=sa && good[x][a].fi+1 >= good[i][b].fi)){
					good[x][a].fi++;
					fin.pb(good[x][a]);
					vis[good[x][a].se] = 1;
					
					good[x][a].fi--;
					a++;
				}else{
					fin.pb(good[i][b]);
					vis[good[i][b].se] = 1;
					b++;
				}
				while(a<sa && vis[good[x][a].se])a++;
				while(b<sb && vis[good[i][b].se])b++;
			}
			good[x].pop_back();
			for(auto z:fin)vis[z.se] = 0;
			swap(good[i],fin);
		}
	}
	cout<<'\n';
	while(q--){
		int t,y;
		cin>>t>>y;
		vector<int>c(y);
		for(int i=0;i<y;i++){
			cin>>c[i];
			take[c[i]] = 1;
		}
		int ans = -1;
		if(y>=sq){
			for(int i=1;i<=n;i++)dp[i] = -1;
			dp[t] = 0;
			if(!take[t])ans = 0;
			for(int i=t-1;i;i--){
				for(int x:adj[i]){
					if(dp[x]!=-1)dp[i] = max(dp[i],dp[x]+1);
				}
				if(!take[i])ans = max(ans,dp[i]);
			}
		}else{
			for(auto x:good[t]){
				if(!take[x.se]){
					ans = x.fi;
					break;
				}
			}
			if(!take[t])ans = max(ans,0);
		}
		cout<<ans<<'\n';
		for(int i=0;i<y;i++)take[c[i]] = 0;
	}
	
}

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