제출 #1239184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239184		pvb.tunglam	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	4 ms	7492 KiB

bitaro

#include <bits/stdc++.h>
#define hash _hash_ 
#define y1 _y1_
#define left _left_ 
#define right _right_
#define dec _dec_   	
using namespace std;

using ll = long long;
using ull = unsigned long long;

	/*----------- I alone decide my fate! ------------*/
/*  I just do what I gotta, in the heat of the summer...  */

int N, M, Q, busy[100009];
bool ban[100009];
vector <pair <int, int> > best[100009];
vector <int> adj[100009], radj[100009];
const int sz = 320; // chia can truy van

void merge(vector<pair<int,int> > &dst, const vector<pair<int,int> > &src)
{
    pair<int,int> buf[2 * sz];
    int i = 0, j = 0, p = 0;
    int na = dst.size(), nb = src.size();
    while ((i < na || j < nb) && p < sz) {
        pair<int,int> cand;
        if (j == nb || (i < na && dst[i].first >= src[j].first + 1)) 
			cand = dst[i++];
        else {
            cand = {src[j].first + 1, src[j].second};
            ++j;
    	}
        bool dup = false;
        for (int k = 0; k < p; ++k) {
            if (buf[k].second == cand.second) {
                dup = true;
                break;
            }
        }
        if (!dup) buf[p++] = cand;
    }
    dst.assign(buf, buf + p);
}

int dp[100009];
int calc(int u) {
	if (dp[u]) return dp[u];
	if (!ban[u]) dp[u] = 0;
	else dp[u] = -1e9;
	for (auto v : radj[u]) {
		dp[u] = max(dp[u], calc(v) + 1);
	}
	return dp[u];
}

void solve() {
	cin >> N >> M >> Q;
	for (int i = 1; i <= M; i ++) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		radj[v].push_back(u);
	} 
	
	// chuan bi cho truy van nhe
	for (int i = 1; i <= N; i ++) {
		best[i].push_back({0, i});
	}
	for (int u = 1; u <= N; u ++) {
		for (auto v : adj[u]) merge(best[v], best[u]);
	}
	
	while (Q --) {
		int x, num; cin >> x >> num;
		for (int i = 1; i <= num; i ++) {
			cin >> busy[i];
			ban[busy[i]] = 1; 
		}
		if (num < sz) {
			int res = 0;
			for (auto p : best[x]) {
				if (!ban[p.second]) {
					res = p.first;
					break;
				}
			}
			cout << res << "\n";
		}
		else {
			cout << calc(x) << "\n";
			for (int i = 1; i <= N; i ++) dp[i] = 0;
		}
		for (int i = 1; i <= num; i ++) ban[busy[i]] = 0;
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	solve();
}


/*
  How can you see into my eyes, like open doors?
  Leading you down into my core, where I've become so numb
  Without a soul, my spirit's sleeping somewhere cold
  Until you find it here and bring it back home!
  Wake me up! Wake me up inside
  Cant wake up? Wake me up inside
*/

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