Submission #1040266

#TimeUsernameProblemLanguageResultExecution timeMemory
1040266shezittElection Campaign (JOI15_election_campaign)C++14
100 / 100
148 ms57004 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; #define int ll #define fore(a, b, c) for(int a=b; a<c; ++a) #define vi vector<int> #define pb push_back #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define F first #define S second #define ii pair<int,int> #define dbg(x) cerr << #x << ": " << x << endl #define raya cerr << "=============" << endl const int N = 2e5+5; const int LG = 20; struct fenwick { int n; vi t; fenwick(int n) : n(n) { t.assign(n+5, 0); } void add(int i, int x){ for(; i<=n; i+=i&-i){ t[i] += x; } } int query(int i){ int r = 0; for(; i>0; i-=i&-i){ r += t[i]; } return r; } } bit(N-5); vi adj[N]; vector<array<int,3>> ways[N]; int dp[N][2]; int pa[N][LG]; int dep[N]; int timer; int entro[N], salgo[N]; int n, m; void dfs(int at, int ante=0){ entro[at] = ++timer; pa[at][0] = ante; for(int u : adj[at]){ if(u == ante) continue; dep[u] = dep[at] + 1; dfs(u, at); } salgo[at] = timer; } int jump(int a, int k){ fore(i, 0, LG){ if((k >> i) & 1){ a = pa[a][i]; } } return a; } int lca(int a, int b){ if(dep[a] > dep[b]) swap(a, b); b = jump(b, dep[b] - dep[a]); if(a == b) return a; for(int i=LG-1; i>=0; --i){ if(pa[a][i] != pa[b][i]){ a = pa[a][i]; b = pa[b][i]; } } return pa[a][0]; } int f(int at, int tomo){ int &res = dp[at][tomo]; if(res > -1) return res; res = 0; if(tomo == 0){ int cur = 0; for(int u : adj[at]){ if(u == pa[at][0]) continue; cur += max(f(u, 0), f(u, 1)); } res = cur; } if(tomo == 1){ int sintomar = f(at, 0); int mx = sintomar; for(auto [a, b, c] : ways[at]){ int tmp = bit.query(entro[a]) + bit.query(entro[b]) + c; mx = max(mx, sintomar + tmp); } res = mx; // tomando bit.add(entro[at], sintomar - res); bit.add(salgo[at]+1, res - sintomar); } return res; } signed main(){ memset(dp, -1, sizeof dp); cin >> n; fore(i, 1, n){ int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } dfs(1); for(int i=1; i<LG; ++i){ for(int j=1; j<=n; ++j){ pa[j][i] = pa[pa[j][i-1]][i-1]; } } cin >> m; fore(i, 0, m){ int a, b, c; cin >> a >> b >> c; ways[lca(a, b)].pb({a, b, c}); } int ans = max(f(1, 0), f(1, 1)); cout << ans << endl; }

Compilation message (stderr)

election_campaign.cpp: In function 'll f(ll, ll)':
election_campaign.cpp:102:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |         for(auto [a, b, c] : ways[at]){
      |                  ^
#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...