diff options
author | Anthony Wang | 2022-03-15 20:38:51 -0500 |
---|---|---|
committer | Anthony Wang | 2022-03-15 20:38:51 -0500 |
commit | 896c6ceeff605c935a5538e3d9eca40ea3c79c56 (patch) | |
tree | 69d97b50f5ced801f6043cbef0219a941239f892 /15.5 | |
parent | 4c488e4c73f2d0e2b96bf0c444c05d42e566dd11 (diff) |
Restructure directories AGAIN so contests from the same season are in the same directory
Diffstat (limited to '15.5')
-rw-r--r-- | 15.5/dec/plat/maxflow.cpp | 59 | ||||
-rw-r--r-- | 15.5/open/plat/landscape.cpp | 70 |
2 files changed, 129 insertions, 0 deletions
diff --git a/15.5/dec/plat/maxflow.cpp b/15.5/dec/plat/maxflow.cpp new file mode 100644 index 0000000..88f3cda --- /dev/null +++ b/15.5/dec/plat/maxflow.cpp @@ -0,0 +1,59 @@ +#include <algorithm> +#include <fstream> +#include <vector> +#include <cmath> +using namespace std; + +int N, ans = 0, pre[50005], d[50005] = { 0 }, L[20][50005] = { 0 }; +vector<int> G[50005]; + +void dfs(int u, int p) { + d[u] = d[p] + 1; + L[0][u] = p; + for (int i = 0; (1 << i) < N; i++) if (L[i][u]) L[i + 1][u] = L[i][L[i][u]]; + for (int v : G[u]) if (v != p) dfs(v, u); +} + +int lca(int u, int v) { + if (d[u] > d[v]) swap(u, v); + for (int i = log2(N); i >= 0; i--) if (d[v] - (1 << i) >= d[u]) v = L[i][v]; + if (u == v) return u; + for (int i = log2(N); i >= 0; i--) if (L[i][u] && L[i][u] != L[i][v]) u = L[i][u], v = L[i][v]; + return L[0][u]; +} + +void solve(int u, int p) { + for (int v : G[u]) { + if (v != p) { + solve(v, u); + pre[u] += pre[v]; + } + } + ans = max(pre[u], ans); +} + +int main() { + ifstream cin("maxflow.in"); + ofstream cout("maxflow.out"); + + int K; + cin >> N >> K; + for (int i = 0; i < N - 1; i++) { + int x, y; + cin >> x >> y; + G[x].push_back(y); + G[y].push_back(x); + } + + dfs(1, 0); + + while (K--) { + int s, t; + cin >> s >> t; + pre[s]++, pre[t]++; + pre[L[0][lca(s, t)]]--, pre[lca(s, t)]--; + } + + solve(1, 0); + cout << ans << endl; +} diff --git a/15.5/open/plat/landscape.cpp b/15.5/open/plat/landscape.cpp new file mode 100644 index 0000000..46e8d8e --- /dev/null +++ b/15.5/open/plat/landscape.cpp @@ -0,0 +1,70 @@ +#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; + +vi A, B; +priority_queue<ll> p1, p2; + +int main() { + init_io("landscape"); + + ll N, X, Y, Z, ans = 0; + cin >> N >> X >> Y >> Z; + for (int i = 0; i < N; i++) { + int A, B; + cin >> A >> B; + for (int j = A; j < B; j++) { + ll cost = X; + if (!p2.empty() && i * Z - p2.top() < X) { + cost = i * Z - p2.top(); + p2.pop(); + } + ans += cost; + p1.push(i * Z + cost); + } + for (int j = B; j < A; j++) { + ll cost = Y; + if (!p1.empty() && i * Z - p1.top() < Y) { + cost = i * Z - p1.top(); + p1.pop(); + } + ans += cost; + p2.push(i * Z + cost); + } + } + cout << ans << endl; +} |