oj.uz

Submission #1000678

# Submission time Handle Problem Language Result Execution time Memory
1000678 2024-06-18T07:08:05 Z vuavisao September (APIO24_september) C++17
25 / 100
 1000 ms 3380 KB 
#include "september.h"
 
#include <vector>
#include <bits/stdc++.h>
using namespace std;
 
const int N = 100'000 + 10;
 
const uint8_t size_T = 2;
const int _1hrd = 100;
const int _1bil = 1000000000;
const array<int, size_T> MOD = {_1bil + 9, _1bil + 11};
const array<int, size_T> BASE = {_1hrd + 28, _1hrd + 31};
 
struct Hash {
	array<int, size_T> val = {0};
	Hash() {};
	Hash (int x) {
		for (uint8_t i = 0; i < size_T; ++ i)
			this->val[i] = x % MOD[i];
	}
 
	bool operator < (const Hash& other) const {
		for (uint8_t i = 0; i < size_T; ++ i)
			if (this->val[i] != other.val[i]) return this->val[i] < other.val[i];
		return false;
	}
 
	bool operator == (const Hash& other) const {
		for (uint8_t i = 0; i < size_T; ++ i)
			if (this->val[i] != other.val[i]) return false;
		return true;
	}
 
	Hash operator + (const int& x) const {
		Hash res;
		for (uint8_t i = 0; i < size_T; ++ i)
			res.val[i] = (1ll * this->val[i] * BASE[i] + x) % MOD[i];
		return res;
	}
 
	Hash operator + (const Hash& other) const {
		Hash res;
		for (uint8_t i = 0; i < size_T; ++ i)
			res.val[i] = (this->val[i] + other.val[i]) % MOD[i];
		return res;
	}
 
	Hash operator - (const Hash& other) const {
		Hash res;
		for (uint8_t i = 0; i < size_T; ++ i) {
			res.val[i] = (this->val[i] - other.val[i]) % MOD[i];
			res.val[i] = (res.val[i] + MOD[i]) % MOD[i];
		}
		return res;
	}
 
	Hash operator * (const Hash& other) const {
		Hash res;
		for (uint8_t i = 0; i < size_T; ++ i)
			res.val[i] = (1ll * this->val[i] * other.val[i]) % MOD[i];
		return res;
	}
 
	friend ostream& operator << (ostream& os, Hash& other) {
		os << "[ ";
		for (uint8_t i = 0; i < size_T; ++ i) {
			cout << other.val[i];
			if(i < size_T - 1) cout << ',';
			cout << ' ';
		}
		os << "]";
		return os;
	}
};
 
int n, m;
int parent[N];
vector<int> g[N];
int perRem[10][N];
 
namespace One {
	bool check() {
		return m == 1;
	}
 
	const int INF = 1'000'000'000;
 
	struct SegTree {
		struct Node {
			int val = -INF;
			Node() {};
			Node(int _val) : val(_val) {};
			Node operator + (const Node& other) const {
				Node res;
				res.val = max(this->val, other.val);
				return res;
			}
		};
	
		int n_node = 0;
		vector<Node> tree = {};
	
		void resize(int _n) { n_node = _n; tree.clear(); tree.resize((n_node << 2) + 10); };
		SegTree() {};
		SegTree(int _n) { this->resize(_n); };
	
		void update(int node, int l, int r, int idx, int val) {
			if (l == r) {
				tree[node].val = val;
				return;
			}
			int mid = (l + r) >> 1;
			if (idx <= mid) update(node << 1, l, mid, idx, val);
			else update(node << 1 | 1, mid + 1, r, idx, val);
			tree[node] = tree[node << 1] + tree[node << 1 | 1];
		}
	
		void Update(int idx, int val) {
			return update(1, 1, n_node, idx, val);
		}
	
		Node query(int node, int l, int r, int L, int R) {
			if (l > r || L > R || l > R || L > r) return Node();
			if (L <= l && r <= R) return tree[node]; 
			int mid = (l + r) >> 1;
			return query(node << 1, l, mid, L, R) + query(node << 1 | 1, mid + 1, r, L, R);
		}
	
		Node Query(int l, int r) {
			return query(1, 1, n_node, l, r);
		}
	};
 
	bool visited[N];
	bool un_visited[N];
	SegTree st;
 
	void dfs(int u, bool save, vector<int>& roll_back) {
		if (visited[u]) return;
		if (save) {
			roll_back.push_back(u);
		}
		visited[u] = true;
		st.Update(u, 0);
		for (const auto& v : g[u]) {
			if (visited[v]) continue;
			dfs(v, save, roll_back);
		}
	}
 
	int dp[N];
 
	int calc() {
		st.resize(n);
		for (int i = 0; i <= n + 1; ++ i) dp[i] = -INF;
		for (int i = 0; i <= n + 1; ++ i) visited[i] = un_visited[i] = false;
		dp[0] = 0;
		for (int i = 0; i < n - 1; ++ i) {
			vector<int> roll_back;
			if (i >= 1) {
				int u = perRem[1][i];
				dfs(u, false, roll_back);
				st.Update(u, -1);
			}
			if (dp[i] < 0) continue;
			for (int j = i + 1; j < n; ++ j) {
				int u = perRem[1][j];
				if (visited[u]) continue;
				un_visited[u] = true;
			}
			for (int j = i + 1; j < n; ++ j) {
				int u = perRem[1][j];
				if (un_visited[u]) {
					dfs(u, true, roll_back);
				}
				st.Update(u, -1);
				if (st.Query(1, n).val < 0) {
					dp[j] = max(dp[j], dp[i] + 1);
				}
			}
			for (int j = i + 1; j < n; ++ j) {
				int u = perRem[1][j];
				if (!un_visited[u]) {
					st.Update(u, 0);
				}
				un_visited[u] = false;
			}
			for (const auto& u : roll_back) {
				visited[u] = false;
				st.Update(u, -INF);
			}
		}
		return dp[n - 1];
	}
}
 
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
	n = N; m = M;
	for (int i = 0; i <= n + 1; ++ i) g[i].clear();
	for (int v = 2; v <= n; ++ v) {
		int u = F[v - 1] + 1;
		g[u].push_back(v);
		// cerr << u << ' ' << v << '\n';
	}
	for (int i = 0; i < m; ++ i) {
		for (int j = 0; j < n - 1; ++ j) {
			perRem[i + 1][j + 1] = S[i][j] + 1;
			// cerr << i + 1 << ' ' << j + 1 << ' ' << perRem[i + 1][j + 1] << ' ' << S[i][j] << '\n';
		}
	}
 
	// if (OneLine::check()) {
	// 	return OneLine::calc();
	// }
	if (One::check()) {
		return One::calc();
	}
	// if (Line::check()) {
	// 	return Line::calc();
	// }
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct

Subtask #2
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Incorrect 1 ms 2652 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2908 KB Output is correct
2 Correct 12 ms 2908 KB Output is correct
3 Correct 32 ms 2908 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 20 ms 2908 KB Output is correct
9 Correct 12 ms 2908 KB Output is correct
10 Correct 32 ms 2908 KB Output is correct
11 Correct 44 ms 2652 KB Output is correct
12 Correct 37 ms 2648 KB Output is correct
13 Correct 35 ms 2652 KB Output is correct
14 Correct 35 ms 2652 KB Output is correct
15 Correct 36 ms 2908 KB Output is correct
16 Correct 6 ms 2648 KB Output is correct
17 Correct 34 ms 2908 KB Output is correct

Subtask #5
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2908 KB Output is correct
2 Correct 12 ms 2908 KB Output is correct
3 Correct 32 ms 2908 KB Output is correct
4 Incorrect 1 ms 3164 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Incorrect 1 ms 2652 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2908 KB Output is correct
2 Correct 12 ms 2908 KB Output is correct
3 Correct 32 ms 2908 KB Output is correct
4 Execution timed out 1042 ms 3380 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #8
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 20 ms 2908 KB Output is correct
9 Correct 12 ms 2908 KB Output is correct
10 Correct 32 ms 2908 KB Output is correct
11 Correct 44 ms 2652 KB Output is correct
12 Correct 37 ms 2648 KB Output is correct
13 Correct 35 ms 2652 KB Output is correct
14 Correct 35 ms 2652 KB Output is correct
15 Correct 36 ms 2908 KB Output is correct
16 Correct 6 ms 2648 KB Output is correct
17 Correct 34 ms 2908 KB Output is correct
18 Execution timed out 1042 ms 3380 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #9
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2908 KB Output is correct
2 Correct 12 ms 2908 KB Output is correct
3 Correct 32 ms 2908 KB Output is correct
4 Incorrect 1 ms 3164 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #10
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Incorrect 1 ms 2652 KB Output isn't correct
9 Halted 0 ms 0 KB -