제출 #1200784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1200784		crispxx	9월 (APIO24_september)	C++20	컴파일 에러	0 ms	0 KiB

september

#include "september.h"

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

#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

#include "stub.cpp"

using lint = __int128;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(l, r) uniform_int_distribution<lint>(l, r)(rng)

int solve(int n, int m, std::vector<int> f, std::vector<std::vector<int>> s) {
	vector<vector<int>> adj(n);
	vector<int> a(n);
	
	for(int i = 1; i < n; i++) {
		adj[f[i]].pb(i);
		a[i] = rnd(1e18, 1e25);
	}
	
	vector<int> tin(n), tout(n);
	
	int timer = 0;
	
	auto dfs = [&](auto &&self, int v) -> void {
		tin[v] = ++timer;
		for(auto to : adj[v]) {
			self(self, to);
		}
		tout[v] = timer;
	};
	
	dfs(dfs, 0);
	
	set<pair<int, int>> st;
	
	for(int i = 1; i < n; i++) {
		st.emplace(tin[i], i);
		// cout << i << ": " << tin[i] << ' ' << tout[i] << nl;
	}
	
	vector<int> mx(n);
	
	for(int i = 0; i < m; i++) {
		for(int j = 0; j < n - 1; j++) {
			int v = s[i][j];
			mx[v] = max(mx[v], j);
		}
	}
	
	int j = 0, k = 0;
	
	vector<lint> sum(m);
	map<lint, int> mp;
	
	auto update = [&](int i, lint x) {
		if(--mp[sum[i]] <= 0) mp.erase(sum[i]);
		sum[i] += x;
		mp[sum[i]]++;
	};
	
	auto update2 = [&](int u) {
		vector<int> del;
		for(auto it = st.lower_bound({tin[u], 0}); it != st.end(); it++) {
			int v = it -> second;
			if(!(tin[v] >= tin[u] && tout[v] <= tout[u])) break;
			k = max(k, mx[v]);
			del.pb(v);
		}
		// cout << "Deleted: ";
		for(auto &x : del) {
			// cout << x << ' ';
			st.erase({tin[x], x});
		}
		// cout << nl;
	};
	
	auto add = [&]() {
		for(int i = 0; i < m; i++) {
			update(i, a[s[i][j]]);
			update2(s[i][j]);
		}
		j++;
	};
	
	int ans = 0;
	
	while(j < n - 1) {
		// cout << nl << ans + 1 << ": " << nl;
		while(j < n - 1 && (mp.size() != 1 || j < k)) {
			add();
			// cout << j + 1 << ' ' << k + 1 << ' ' << mp.size() << nl;
		}
		mp.clear();
		k = 0;
		// cout << nl;
		ans++;
	}
	
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

september.cpp:11:10: fatal error: stub.cpp: No such file or directory
   11 | #include "stub.cpp"
      |          ^~~~~~~~~~
compilation terminated.