Submission #719617

#	Time	Username	Problem	Language	Result	Execution time	Memory
719617		S2speed	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1462 ms	114196 KiB

bitaro

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cout<<"--------------------------------------\n";
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 1e5 + 18 , md = 1e9 + 7 , inf = 2e8;

int n , m , q , sq;
vector<int> adj[maxn] , qu;
vector<pii> f[maxn];
bool mark[maxn];
int dp[maxn];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin>>n>>m>>q; sq = min(n , 100);
	for(int i = 0 ; i < m ; i++){
		int v , u;
		cin>>v>>u; v--; u--;
		adj[u].push_back(v);
	}
	for(int i = 0 ; i < n ; i++){
		vector<pii> tmp;
		tmp.push_back({-1 , i});
		for(auto j : adj[i]){
			for(auto k : f[j]){
				tmp.push_back(k);
			}
		}
		sort(all(tmp) , greater<pii>());
		for(auto p : tmp){
			if(sze(f[i]) == sq) break;
			if(mark[p.second]) continue;
			mark[p.second] = true;
			f[i].push_back({p.first + 1 , p.second});
		}
		for(auto p : f[i]){
			mark[p.second] = false;
		}
	}
	for(int e = 0 ; e < q ; e++){
		qu.clear();
		int v , k , res = -1;
		cin>>v>>k; v--;
		for(int i = 0 ; i < k ; i++){
			int u;
			cin>>u; u--;
			qu.push_back(u);
			mark[u] = true;
		}
		if(k < sq){
			for(auto p : f[v]){
				if(mark[p.second]) continue;
				res = p.first;
				break;
			}
		} else {
			for(int i = 0 ; i <= v ; i++){
				int h = (mark[i] ? -inf : 0);
				for(auto j : adj[i]){
					h = max(dp[j] + 1 , h);
				}
				dp[i] = h;
			}
			res = (dp[v] < 0 ? -1 : dp[v]);
		}
		cout<<res<<'\n';
		for(auto u : qu){
			mark[u] = false;
		}
	}
	return 0;
}

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