aboutsummaryrefslogtreecommitdiff
path: root/12.5
diff options
context:
space:
mode:
authorAnthony Wang2022-03-15 20:38:51 -0500
committerAnthony Wang2022-03-15 20:38:51 -0500
commit896c6ceeff605c935a5538e3d9eca40ea3c79c56 (patch)
tree69d97b50f5ced801f6043cbef0219a941239f892 /12.5
parent4c488e4c73f2d0e2b96bf0c444c05d42e566dd11 (diff)
Restructure directories AGAIN so contests from the same season are in the same directory
Diffstat (limited to '12.5')
-rw-r--r--12.5/feb/gold/route.cpp29
-rw-r--r--12.5/nov/gold/bbreeds.cpp14
-rw-r--r--12.5/nov/gold/btree.cpp80
-rw-r--r--12.5/open/gold/yinyang.cpp97
4 files changed, 220 insertions, 0 deletions
diff --git a/12.5/feb/gold/route.cpp b/12.5/feb/gold/route.cpp
new file mode 100644
index 0000000..aab04ed
--- /dev/null
+++ b/12.5/feb/gold/route.cpp
@@ -0,0 +1,29 @@
+#include <algorithm>
+#include <iostream>
+using namespace std;
+constexpr auto INF = (int)1e9;
+typedef pair<int, int> ii;
+
+int l[40005], r[40005], dl[40005] = { 0 }, dr[40005] = { 0 };
+ii E[100005];
+
+int main() {
+ int N, M, R;
+ cin >> N >> M >> R;
+ for (int i = 0; i < N; i++) cin >> l[i];
+ for (int i = 0; i < M; i++) cin >> r[i];
+ for (int i = 0; i < R; i++) cin >> E[i].first >> E[i].second;
+
+ sort(E, E + R, [](const ii& a, const ii& b) { return a.first + a.second < b.first + b.second; });
+
+ for (int i = 0; i < N; i++) dl[i] = l[i];
+ for (int i = 0; i < M; i++) dr[i] = r[i];
+
+ for (int i = 0; i < R; i++) {
+ int u = E[i].first, v = E[i].second, a = dl[--u], b = dr[--v];
+ dl[u] = max(l[u] + b, dl[u]);
+ dr[v] = max(r[v] + a, dr[v]);
+ }
+
+ cout << max(*max_element(dl, dl + N), *max_element(dr, dr + N)) << endl;
+}
diff --git a/12.5/nov/gold/bbreeds.cpp b/12.5/nov/gold/bbreeds.cpp
new file mode 100644
index 0000000..9d7a745
--- /dev/null
+++ b/12.5/nov/gold/bbreeds.cpp
@@ -0,0 +1,14 @@
+#include <iostream>
+#include <string>
+using namespace std;
+
+int main() {
+ string S; cin >> S;
+ int x = 0, DP[1005] = { 1 };
+ for (auto c : S) {
+ if (c == '(') for (x++, int i = x; i > 0; i--) DP[i] = (DP[i - 1] + DP[i]) % 2012;
+ else for (x--, int i = 0; i <= x; i++) DP[i] = (DP[i] + DP[i + 1]) % 2012;
+ DP[x + 1] = 0;
+ }
+ cout << DP[0] << endl;
+}
diff --git a/12.5/nov/gold/btree.cpp b/12.5/nov/gold/btree.cpp
new file mode 100644
index 0000000..16462ab
--- /dev/null
+++ b/12.5/nov/gold/btree.cpp
@@ -0,0 +1,80 @@
+#include <algorithm>
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <vector>
+#include <queue>
+#include <set>
+#include <map>
+#include <unordered_set>
+#include <unordered_map>
+#include <cmath>
+#include <cstring>
+#define init_io(pname) ifstream cin((string)pname+".in"); ofstream cout((string)pname+".out"); ios_base::sync_with_stdio(false); cin.tie(NULL)
+#define FOR(i, a, b, in) for (int i = (a); i < (b); i += in)
+#define REP(i, a, b) for (int i = (a); i < (b); i++)
+#define RFOR(i, a, b, in) for (int i = (a) - 1; i >= (b); i -= in)
+#define RREP(i, a, b) for (int i = (a) - 1; i >= (b); i--)
+#define trav(a, x) for (auto& a : x)
+#define mp make_pair
+#define pb push_back
+#define f first
+#define s second
+#define lb lower_bound
+#define ub upper_bound
+#define sz(x) (int)x.size()
+#define all(x) begin(x), end(x)
+#define rsz resize
+#define mem(a, b) memset(a, (b), sizeof(a))
+using namespace std;
+typedef string str;
+typedef long long ll;
+typedef long double ld;
+typedef pair<int, int> ii; typedef pair<ll, ll> pl; typedef pair<ld, ld> pd;
+typedef vector<int> vi; typedef vector<ll> vl; typedef vector<ld> vd;
+typedef vector<ii> vii; typedef vector<pl> vpl; typedef vector<pd> vpd;
+constexpr auto INF = (int)1e9;
+constexpr auto LINF = (ll)1e18;
+
+int L[40005];
+vi G[40005];
+map<int, int> A[40005];
+map<int, int, greater<int>> B[40005];
+
+int dfs(int u, int d) {
+ int ret = 0;
+ L[u] == 1 ? A[u][d] = 1 : B[u][d] = 1;
+ for (auto& v : G[u]) {
+ ret = max(dfs(v, L[v] + d), ret);
+ for (auto& x : A[v]) {
+ if (B[u].find(2 * d - L[u] - x.first) != B[u].end()) { // Match left side with corresponding right side
+ ret = max(max(x.second, B[u][2 * d - L[u] - x.first]), ret);
+ }
+ }
+ for (auto& x : B[v]) {
+ if (A[u].find(2 * d - L[u] - x.first) != A[u].end()) { // Match right side with corresponding left side
+ ret = max(max(x.second, A[u][2 * d - L[u] - x.first]), ret);
+ }
+ }
+ for (auto& x : A[v]) A[u][x.first] = max(max(x.first - d, x.second), A[u][x.first]); // Merge A[v] to A[u], adjust max nesting depth accordingly
+ for (auto& x : B[v]) B[u][x.first] = max(max(d - x.first, x.second), B[u][x.first]); // Merge B[v] to B[u], adjust max nesting depth accordingly
+ A[v].clear(), B[v].clear();
+ }
+ while (!A[u].empty() && A[u].begin()->first < d) A[u].erase(A[u].begin());
+ while (!B[u].empty() && B[u].begin()->first > d) B[u].erase(B[u].begin());
+ return ret;
+}
+
+int main() {
+ init_io("btree");
+ int N; cin >> N;
+ for (int i = 1; i < N; i++) {
+ int p; cin >> p;
+ G[--p].push_back(i);
+ }
+ for (int i = 0; i < N; i++) {
+ char c; cin >> c;
+ L[i] = (c == '(' ? 1 : -1);
+ }
+ cout << dfs(0, L[0]);
+}
diff --git a/12.5/open/gold/yinyang.cpp b/12.5/open/gold/yinyang.cpp
new file mode 100644
index 0000000..9ce4aec
--- /dev/null
+++ b/12.5/open/gold/yinyang.cpp
@@ -0,0 +1,97 @@
+#include <algorithm>
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <vector>
+#include <queue>
+#include <set>
+#include <map>
+#include <unordered_set>
+#include <unordered_map>
+#include <cmath>
+#include <cstring>
+#define init_io(pname) ifstream cin((string)pname+".in"); ofstream cout((string)pname+".out"); ios_base::sync_with_stdio(false); cin.tie(NULL)
+#define FOR(i, A, B, in) for (int i = (A); i < (B); i += in)
+#define REP(i, A, B) for (int i = (A); i < (B); i++)
+#define RFOR(i, A, B, in) for (int i = (A) - 1; i >= (B); i -= in)
+#define RREP(i, A, B) for (int i = (A) - 1; i >= (B); i--)
+#define trav(A, x) for (auto& A : x)
+#define mp make_pair
+#define pb push_back
+#define lb lower_bound
+#define ub upper_bound
+#define sz(x) (int)x.size()
+#define all(x) begin(x), end(x)
+#define rsz resize
+#define mem(A, B) memset(A, (B), sizeof(A))
+#define uset unordered_set
+#define umap unordered_map
+using namespace std;
+typedef string str;
+typedef long long ll;
+typedef long double ld;
+typedef pair<int, int> ii; typedef pair<ll, ll> pl; typedef pair<ld, ld> pd;
+typedef vector<int> vi; typedef vector<ll> vl; typedef vector<ld> vd;
+typedef vector<ii> vii; typedef vector<pl> vpl; typedef vector<pd> vpd;
+constexpr auto INF = (int)1e9;
+constexpr auto LINF = (ll)1e18;
+
+vii G[100005];
+umap<int, int> A[100005], B[100005];
+
+ll dfs(int u, int p, int s) {
+ ll ret = 0;
+ for (auto& v : G[u]) { // Traverse children
+ if (v.first != p) ret += dfs(v.first, u, s + (v.second ? 1 : -1));
+ }
+ int m = 0; // Computed largest set to merge small to large
+ for (auto& v : G[u]) {
+ if (v.first != p && A[v.first].size() + B[v.first].size() > A[m].size() + B[m].size()) m = v.first;
+ }
+ if (A[m].find(s) != A[m].end()) {
+ ret += B[m][s];
+ B[u][s] += A[m][s];
+ A[m].erase(s);
+ }
+ if (A[u].size() < A[m].size()) swap(A[u], A[m]);
+ if (B[u].size() < B[m].size()) swap(B[u], B[m]);
+ for (auto& x : A[m]) A[u][x.first] += x.second;
+ for (auto& x : B[m]) B[u][x.first] += x.second;
+ // Merge other sets
+ for (auto& v : G[u]) {
+ if (v.first != p && v.first != m) {
+ for (auto& x : A[v.first]) {
+ if (B[u].find(2 * s - x.first) != B[u].end()) ret += (ll)x.second * B[u][2 * s - x.first];
+ }
+ for (auto& x : B[v.first]) {
+ if (A[u].find(2 * s - x.first) != A[u].end()) ret += (ll)x.second * A[u][2 * s - x.first];
+ if (B[u].find(2 * s - x.first) != B[u].end()) ret += (ll)x.second * B[u][2 * s - x.first];
+ }
+ if (A[v.first].find(s) != A[v.first].end()) {
+ ret += B[v.first][s];
+ B[u][s] += A[v.first][s];
+ A[v.first].erase(s);
+ }
+ if (A[u].size() < A[v.first].size()) swap(A[u], A[v.first]);
+ if (B[u].size() < B[v.first].size()) swap(B[u], B[v.first]);
+ for (auto& x : A[v.first]) A[u][x.first] += x.second; // Merge "A" sets
+ for (auto& x : B[v.first]) B[u][x.first] += x.second; // Merge "B" sets
+ }
+ }
+ A[u][s]++;
+ return ret;
+}
+
+int main() {
+ init_io("yinyang");
+
+ int N;
+ cin >> N;
+ for (int i = 0; i < N - 1; i++) {
+ int A, B, t;
+ cin >> A >> B >> t;
+ G[A].emplace_back(B, t);
+ G[B].emplace_back(A, t);
+ }
+ cout << dfs(1, 0, 0) << endl;
+}