Submission #1311805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311805		ppmn_6	September (APIO24_september)	C++20	100 / 100	151 ms	7028 KiB

september

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// https://codeforces.com/blog/entry/79148
class Timer: chrono::high_resolution_clock {
    const time_point start_time;
public:
    Timer(): start_time(now()) {}
    rep elapsed_time() const {
		return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count();
	}
} timer;

int solve(int n, int m, vector<int> p, vector<vector<int>> s) {
	vector<array<int, 2>> segs(n, {n, -1});
	segs[0] = {-1, -1};
	for (int i = 0; i < m; i++) {
		vector<int> rev(n), cnt(n, 0);
		for (int j = 0; j < n - 1; j++) {
			rev[s[i][j]] = j;
			segs[s[i][j]][0] = min(segs[s[i][j]][0], j);
			segs[s[i][j]][1] = max(segs[s[i][j]][1], j);
		}
		for (int i = 1; i < n; i++) {
			cnt[p[i]]++;
		}
		queue<int> q;
		for (int i = 0; i < n; i++) {
			if (!cnt[i]) {
				q.push(i);
			}
		}
		while (q.size()) {
			int u = q.front();
			q.pop();
			if (!u) {
				break;
			}
			segs[p[u]][1] = max(segs[p[u]][1], segs[u][1]);
			cnt[p[u]]--;
			if (!cnt[p[u]]) {
				q.push(p[u]);
			}
		}
	}
	sort(segs.begin(), segs.end());
	vector<int> ans(n - 1);
	ans[0] = 1;
	int pos = 1, cur = 1;
	for (int i = 1; i < n; i++) {
		if (pos > segs[i][1]) {
			continue;
		}
		if (pos == segs[i][0]) {
			cur++;
		}
		while (pos <= segs[i][1]) {
			ans[pos] = cur;
			pos++;
		}
	}
	return ans[n - 2];
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 11 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 9 / 9
• Subtask 10: 16 / 16