제출 #1322100

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1322100		lwham	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	3 ms	5432 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 1e5;
const int sq = 335;

vector<int> adj[maxn],in[maxn];
set<pair<int,int>> st[maxn];
int u,v,q,n,m,y,c,h,currt[maxn],res;

void inp(){
	cin >> n >> m >> q;
	for (int i = 1 ; i <= m; i++){
		cin >> u >> v;
		adj[u].push_back(v);
		in[v].push_back(u);
	}
}
void prep(){
	for (int i = 1 ; i <= n ; i++){
		st[i].insert({0, i});
	}
	for (int i = 1 ; i <= n ; i++){
		set<pair<int,int>> bag;
		for (auto it : in[i]){
			for (auto el : st[it]){
				bag.insert(el);
			}
		}
		vector<bool> is(n+1, false);
		while ((int)bag.size() && (int)st[i].size() < sq){
			pair<int,int> p = *bag.rbegin();
			bag.erase(*bag.rbegin());
			if (is[p.second]) continue;
			is[p.second] = true;
			st[i].insert({p.first + 1, p.second});
		}
	}
}
void query(){
	while (q--){
		cin >> h >> y;
		for (int i = 1 ; i <= y ; i++){
			cin >> c;
			currt[c] = q;
		}
		if (y < sq){
			res = 0;
			for (auto it : st[h]){
				if (currt[it.second] != q){
					res = max(res, it.first);
				}
			}
		}
		else{ // dp
			vector<int> dp(n+1, -1);
			res = 0;
			dp[h] = 0;
			for (int i = n-1 ; i >= 1 ; i--){
				for (auto it : adj[i]){
					if (dp[it] == -1) continue;
					dp[i] = max(dp[it] + 1, dp[i]);
				}
				if (currt[i] != q) res = max(res, dp[i]);
			}
		}
		cout << res << '\n';
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	memset(currt, -1, sizeof currt);
	inp();
	prep();
	query();
}

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