Submission #330526

#	Time	Username	Problem	Language	Result	Execution time	Memory
330526		pit4h	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2094 ms	14256 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 = 300;
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 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) {
		vector<pii> nvec;
		nvec.push_back({0, i});
		pii mini = mp(0, 0);
		for(int j: g[i]) {
			mini = max(mini, mp(vec[j].back().st, j));
		}
		for(int j: g[i]) {
			for(auto k: vec[j]) {
				if(j==mini.nd || k.st > mini.st) nvec.push_back(mp(k.st+1, k.nd));
			}
		}
		sort(nvec.rbegin(), nvec.rend());
			
		for(auto j: nvec) {
			if(vis[j.nd]) continue;
			vis[j.nd] = 1;
			vec[i].push_back(j);
			if((int)vec[i].size()>=Bucket) {
				break;
			}
		}
		for(auto j: nvec) {
			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: 0 / 7
• Subtask 3: 0 / 86