5 files changed, 118 insertions, 0 deletions
diff --git a/19/day1/out b/19/day1/out
new file mode 100644
index 0000000..67f3f23
--- /dev/null
+++ b/19/day1/out
@@ -0,0 +1 @@
+270
diff --git a/19/day1/palindrometer.cpp b/19/day1/palindrometer.cpp
new file mode 100644
index 0000000..65914fa
--- /dev/null
+++ b/19/day1/palindrometer.cpp
@@ -0,0 +1,22 @@
+#include <bits/stdc++.h>
+using namespace std;
+using ll = long long;
+
+int P[2][100001];
+
+int main() {
+	string S; cin >> S;
+	int N = S.size();
+	for (int i = 0; i < 2; ++i) {
+		for (int j = 0, l = 0, r = 0; j < N; ++j) {
+			int k = (j > r ? !i : min(P[i][l + r - j + i], r - j + 1));
+			while (j - k - i >= 0 && j + k < N && S[j - k - i] == S[j + k]) ++k;
+			P[i][j] = k--;
+			if (j + k > r) l = j - k - i, r = j + k;
+		}
+	}
+
+	ll ans = 0;
+	for (int i = 0; i < N; ++i) ans += P[0][i] + P[1][i];
+	cout << ans << '\n';
+}
+\ No newline at end of file
diff --git a/19/day1/retemordnilap.cpp b/19/day1/retemordnilap.cpp
new file mode 100644
index 0000000..991bc78
--- /dev/null
+++ b/19/day1/retemordnilap.cpp
@@ -0,0 +1,42 @@
+#include <bits/stdc++.h>
+using namespace std;
+using ll = long long;
+
+int main() {
+	char s[10] = "MMOOMO";
+	int K;
+	cin >> K;
+	if (K == 5) {
+		cout << "impossible";
+		return 0;
+	}
+	if (K == 1) { cout << "O"; return 0; }
+	if (K == 2) { cout << "MO"; return 0; }
+	if (K == 3) { cout << "MM";	return 0; }
+	if (K == 7) { cout << "MMMO"; return 0; }
+	if (K == 9) { cout << "MOMOM"; return 0; }
+	if (K % 2 == 0 && K / 2 <= 1e5) {
+		for (int i = 0; i <= K / 2; ++i) cout << s[i % 6];
+		return 0;
+	}
+	ll sq = sqrt(8ll * K + 1) + 0.5;
+	if (sq * sq == 8ll * K + 1) {
+		int t = (sq - 1) / 2;
+		for (int i = 0; i < t; ++i) cout << "O";
+		return 0;
+	}
+	/*if (K > 1e8 && K % 2 == 1) {
+		cout << "M";
+		--K;
+	}*/
+	int t = sqrt(2 * K);
+	while ((((K - t * (t + 1) / 2) - 2) % 2) || K - t * (t + 1) / 2 - 2 < 6) --t;
+	for (int i = 0; i < t; ++i) cout << "O";
+	int ans = t;
+	//cout << t << '\n';
+	K += - t * (t + 1) / 2 - 2;
+	for (int i = 0; i <= K / 2; ++i) cout << s[i % 6];
+	ans += K / 2;
+	assert(ans <= 1e5);
+	//cout << ans << '\n';
+}
+\ No newline at end of file
diff --git a/19/day1/test.sh b/19/day1/test.sh
new file mode 100644
index 0000000..3b4f3f1
--- /dev/null
+++ b/19/day1/test.sh
@@ -0,0 +1,9 @@
+for i in {6..1000}
+do
+	echo $i >> in
+    .vscode/3 < in | .vscode/1 > out
+    if !(cmp -s in out); then
+		echo $i
+	fi
+	rm in
+done
+\ No newline at end of file
diff --git a/19/day1/treedist.cpp b/19/day1/treedist.cpp
new file mode 100644
index 0000000..a2c83ae
--- /dev/null
+++ b/19/day1/treedist.cpp
@@ -0,0 +1,44 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+#define eb emplace_back
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+constexpr int MAXN = 100001;
+constexpr ll INF = 1e9;
+
+int N, Q, H[MAXN];
+bitset<MAXN> ans;
+vector<ii> G[3 * MAXN];
+unordered_map<ll, int> vis;
+
+void solve(int u, int p, int d) {
+	if (d && u <= N) ans[u] = 1;
+	if (d < 0) d = -1;
+	if (vis.find(INF * u + p) != vis.end()) {
+		if (vis[INF * u + p] != d) d = -1;
+		else return;
+	}
+	vis[INF * u + p] = d;
+	for (auto & v : G[u]) if (v.s != p) solve(v.s, u, d - v.f);
+}
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+	cin >> N >> Q;
+	iota(H, H + N + 1, 0);
+	int l = N + 1;
+	for (int i = 1, a, b; i < N; ++i) {
+		cin >> a >> b;
+		G[H[a]].eb(0, l), G[l].eb(0, H[a]), H[a] = l++;
+		G[H[b]].eb(0, l), G[l].eb(0, H[b]),	H[b] = l++;
+		G[H[a]].eb(1, H[b]), G[H[b]].eb(1, H[a]);
+	}
+	while (Q--) {
+		int a, b; cin >> a >> b;
+		solve(a, 0, b);
+	}
+	cout << N - ans.count() << '\n';
+	for (int i = 1; i <= N; ++i) if (!ans[i]) cout << i << '\n';
+}
+\ No newline at end of file