Submission #1209231

#TimeUsernameProblemLanguageResultExecution timeMemory
1209231veplsnxElection Campaign (JOI15_election_campaign)C++20
20 / 100
73 ms22976 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define u128 unsigned __int128 #define i128 __int128 #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define pb push_back #define eb emplace_back #define mt make_tuple #define mp make_pair #define pii pair<int, int> #define pll pair<ll, ll> #define pli pair<ll, int> #define pil pair<int, ll> #define ff first #define ss second const ll inf = 9e18; const int iinf = 2e9; const int N = 1e5; const ll MOD = 1e9 + 7; vector<vector<int>> g; vector<vector<int>> up; vector<int> depth, ord; int logn; void dfs(int v, int p){ up[v].assign(logn + 1, 1); up[v][0] = p; for (int i = 1; i <= logn; ++i) up[v][i] = up[up[v][i - 1]][i - 1]; for (auto to : g[v]){ if (to != p){ depth[to] = depth[v] + 1; dfs(to, v); } } ord.pb(v); } int lca(int u, int v){ if (depth[u] < depth[v]) swap(u, v); int dlt = depth[u] - depth[v]; for (int k = logn; k > -1; --k) if ((1 << k) & dlt) u = up[u][k]; if (u == v) return u; for (int k = logn; k > -1; --k){ int nu = up[u][k], nv = up[v][k]; if (nu != nv){ u = nu; v = nv; } } return up[u][0]; } void solution(){ int n; cin >> n; g.resize(n + 1); up.resize(n + 1); depth.assign(n + 1, 0); logn = ceil(log2(n)); bool case23 = true; bool case4 = true; for (int i = 0; i < n - 1; ++i){ int x, y; cin >> x >> y; g[x].pb(y); g[y].pb(x); case23 &= (abs(x - y) == 1); } int m; cin >> m; vector<pair<int, int>> v(m); vector<int> c(m); for (int i = 0; i < m; ++i){ cin >> v[i].ff >> v[i].ss >> c[i]; if (v[i].ff > v[i].ss) swap(v[i].ff, v[i].ss); case4 &= (c[i] == 1); } if (case23){ vector<pair<int, int>> vn(m); vector<int> order(m), cn(m); iota(all(order), 0); sort(all(order), [&](int i, int j){ return v[i].ss < v[j].ss; }); for (int i = 0; i < m; ++i){ vn[i] = v[order[i]]; cn[i] = c[order[i]]; } vector<int> vr(m); for (int i = 0; i < m; ++i) vr[i] = vn[i].ss; vector<ll> dp(m, 0); for (int i = 0; i < m; ++i){ int l = vn[i].ff, r = vn[i].ss; int idx = int(upper_bound(all(vr), l - 1) - vr.begin() - 1); dp[i] = max((i == 0 ? 0 : dp[i - 1]), (idx == -1 ? 0 : dp[idx]) + cn[i]); } cout << dp[m - 1]; } else if (m <= 15){ dfs(1, 1); vector<vector<int>> el(m); for (int i = 0; i < m; ++i){ int a = v[i].ff, b = v[i].ss; int lc = lca(a, b); while (a != lc){ el[i].pb(a); a = up[a][0]; } el[i].pb(lc); while (b != lc){ el[i].pb(b); b = up[b][0]; } } vector<vector<bool>> can(m, vector<bool>(m, false)); for (int i = 0; i < m; ++i){ for (int j = i + 1; j < m; ++j){ vector<int> used(n + 1, 0); for (int k = 0; k < sz(el[i]); ++k) used[el[i][k]] = 1; bool ok = true; for (int k = 0; k < sz(el[j]) && ok; ++k) if (used[el[j][k]]) ok = false; can[i][j] = ok; } } int M = (1 << m) - 1; ll ans = 0; for (int k = 0; k <= M; ++k){ vector<int> bits; for (int i = 0; (1 << i) <= k; ++i) if ((1 << i) & k) bits.pb(i); bool ok = true; for (int i = 0; i < sz(bits) && ok; ++i) for (int j = i + 1; j < sz(bits) && ok; ++j) if (!can[bits[i]][bits[j]]) ok = false; if (!ok) continue; ll curr = 0; for (int i : bits) curr += c[i]; ans = max(ans, curr); } cout << ans; } else if (n <= 1000 && m <= 1000){ vector<vector<tuple<int, int, int>>> p(n + 1); vector<ll> dp(n + 1, 0); dfs(1, 1); for (int i = 0; i < m; ++i){ int l = lca(v[i].ff, v[i].ss); p[l].pb(mt(v[i].ff, v[i].ss, c[i])); } for (int vert : ord){ ll base = 0; for (auto to : g[vert]) if (to != up[vert][0]) base += dp[to]; dp[vert] = base; for (auto [l, r, cost] : p[vert]){ ll otn = 0; while (l != vert){ otn += dp[l]; l = up[l][0]; } while (r != vert){ otn += dp[r]; r = up[r][0]; } dp[vert] = max(dp[vert], base - otn + cost); } } cout << dp[1]; } else if (case4){ } else{ } } signed main(/* Kurmankul Nurislam */){ //freopen("fcolor.in", "r", stdin); //freopen("fcolor.out", "w", stdout); cin.tie(nullptr) -> sync_with_stdio(false); int t = 1; //cin >> t; while (t--){ solution(); //cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...