Submission #330528

#	Time	Username	Problem	Language	Result	Execution time	Memory
330528		pit4h	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1639 ms	424300 KiB

bitaro

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#ifndef LOCAL
#define cerr if(0)cerr
#endif
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using pii = pair<int, int>;

const int N = 1e5+1, M = 2e5+1, Bucket = 400;
int n, m, q, t[N], s[N];
int ans[N];
vector<int> g[N], block[N], queries[N];
vector<pii> vec[N];

bool vis[N], blocked[N];
int calc[N];
int brute(int x) {
	if(vis[x]==1) {
		return calc[x];
	}
	vis[x] = 1;
	calc[x] = 0;
	int res = 0;
	for(int i: g[x]) {
		res = max(res, brute(i)+1);	
	}
	if(res==0 && blocked[x]) {
		res = -1;
	}
	calc[x] = res;
	return res;
}
int ptr[N];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m>>q;
	for(int i=0; i<m; ++i) {
		int a, b; cin>>a>>b;
		g[b].push_back(a);
	}
	for(int i=0; i<q; ++i) {
		ans[i] = -1;
		cin>>t[i]>>s[i];	
		block[i].resize(s[i]);
		for(int j=0; j<s[i]; ++j) {
			cin>>block[i][j];	
		}
		if(s[i]>=Bucket) {
			for(int j: block[i]) {
				blocked[j] = 1;
			}
			ans[i] = brute(t[i]);
			for(int j=1; j<=n; ++j) {
				vis[j] = blocked[j] = 0;
			}
		}
		else {
			queries[t[i]].push_back(i);	
		}
	}

	for(int i=1; i<=n; ++i) {
		for(int iter=0; iter<Bucket; ++iter) {
			pii best = mp(0, 0);
			for(int j: g[i]) {
				while(ptr[j] < (int)vec[j].size() && vis[vec[j][ptr[j]].nd]) {
					ptr[j]++;
				}
				if(ptr[j] < (int)vec[j].size()) {
					best = max(best, mp(vec[j][ptr[j]].st+1, vec[j][ptr[j]].nd));
				}
			}
			if(best == mp(0, 0)) {
				break;
			}
			vis[best.nd] = 1;
			vec[i].push_back(best);
		}
		if((int)vec[i].size() < Bucket) {
			vec[i].push_back(mp(0, i));
		}

		for(int j: g[i]) {
			ptr[j] = 0;
		}
		for(auto j: vec[i]) {
			vis[j.nd] = 0;
		}

		for(int j: queries[i]) {
			for(int k: block[j]) {
				blocked[k] = 1;
			}
			for(auto k: vec[i]) {
				if(!blocked[k.nd]) {
					ans[j] = k.st;
					break;
				}
			}
			for(int k: block[j]) {
				blocked[k] = 0;
			}
		}
	}


	for(int i=0; i<q; ++i) {
		cout<<ans[i]<<'\n';
	}
	
}

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