Submission #473018

#	Time	Username	Problem	Language	Result	Execution time	Memory
473018		berarchegas	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2075 ms	159796 KiB

bitaro

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define MAXN 100100
#define INF 1e17
#define pb push_back
#define F first
#define S second
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int M = 998244353;
const int X = 800;

vector<int> v[MAXN], w[MAXN];
vector<pii> atual, sq[MAXN];
int vis[MAXN], dp[MAXN];

void merg(int node) {
	atual = sq[node];
	vector<pii> novo;
	for (int i = 0; i < (int)atual.size(); i++) {
		if (i == (int)atual.size() -1 || atual[i].F != atual[i+1].F) novo.pb(atual[i]);
	}
	atual = novo;
	sort(atual.begin(), atual.end(), [&] (pii x, pii y) { return x.S > y.S; });
	while ((int)atual.size() > X) atual.pop_back();
	sq[node] = atual;
	for (pii &x : atual) x.S++;
	sort(atual.begin(), atual.end());
	for (int x : w[node]) {
		novo = sq[x];
		sq[x].resize((int)sq[x].size() + (int)atual.size());
		merge(novo.begin(), novo.end(), atual.begin(), atual.end(), sq[x].begin());
	}
}

void dfs(int node) {
	vis[node] = 1;
	for (int x : v[node]) {
		if (!vis[x]) dfs(x);
		dp[node] = max(dp[node], 1 + dp[x]);
	}
}

int main() { _
	int n, m, q, a, b;
	cin >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		v[b].pb(a);
		w[a].pb(b);
	}
	for (int i = 1; i <= n; i++) sq[i].pb({i, 0});
	for (int i = 1; i <= n; i++) {
		merg(i);
	}
	int d, tot, aux;
	for (int i = 0; i < q; i++) {
		cin >> d >> tot;
		set<int> inv;
		for (int j = 0; j < tot; j++) {
			cin >> aux;
			inv.insert(aux);
		}
		if (tot < X) {
			int ans = -1;
			for (pii x : sq[d]) {
				if (!inv.count(x.F)) ans = max(ans, x.S);
			}
			cout << ans << '\n';
		}
		if (tot >= X) {
			memset(dp, 0, sizeof(dp));
			memset(vis, 0, sizeof(vis));
			dfs(d);
			int ans = -1;
			for (int i = 1; i <= n; i++) {
				if (!inv.count(i)) ans = max(ans, dp[i]);
			}
			cout << ans << '\n';
		}
	}
    return 0;
}
/* stuff you should look for
	* int overflow, array bounds
	* special cases (lowest n, greatest n)
	* RTE MAXN
	* WRITE/DRAW STUFF DOWN
	* DONT OVERCOMPLICATE
*/

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