Submission #947942

#TimeUsernameProblemLanguageResultExecution timeMemory
947942vqpahmadElection Campaign (JOI15_election_campaign)C++14
10 / 100
144 ms82640 KiB
#include<bits/stdc++.h> using namespace std; #ifdef ONPC #include"debug.h" #else #define debug(...) 42 #endif #define endl '\n' #define ll long long #define pii pair<int,int> #define F first #define S second #define pb push_back #define sz(a) (int)a.size() #define all(a) a.begin(),a.end() #define int long long template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } const int mod = 1e9 + 7; const int MAXN = 1e6 + 15; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; vector<int> adj[MAXN]; int fa[MAXN][20], dep[MAXN], dt[MAXN], ft[MAXN], timer = 1; void dfs(int node, int par){ dep[node] = dep[par] + 1; fa[node][0] = par; dt[node] = timer++; for (auto to : adj[node]){ if (to != par) dfs(to, node); } ft[node] = timer++; } int lca(int u, int v){ if (dep[u] > dep[v]) swap(u, v); for (int j = 19; j >= 0; j--){ if (dep[fa[v][j]] >= dep[u]) v = fa[v][j]; } if (u == v) return u; for (int j = 19; j >= 0; j--){ if (fa[v][j] != fa[u][j]) v = fa[v][j], u = fa[u][j]; } return fa[u][0]; } vector<array<int, 3>> queries[MAXN]; ll dp[MAXN]; bool contain(int u, int v){ return dt[u] <= dt[v] && ft[v] <= ft[u]; } void solve(int node, int par){ for (int to : adj[node]){ if (to != par) { solve(to, node); dp[node] += dp[to]; } } for (auto [u, v, c] : queries[node]){ ll tm = c; for (int to : adj[u]){ if (contain(to, v) || contain(to, u)) continue; tm += dp[to]; } for (int to : adj[v]){ if (contain(to, v) || contain(to, u)) continue; tm += dp[to]; } if (node != u && node != v){ for (int to : adj[node]){ if (contain(to, v) || contain(to, u)) continue; tm += dp[to]; } } ckmax(dp[node], tm); } } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for (int i = 0; i < n - 1; i++){ int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } dfs(1, 1); for (int j = 1; j < 20; j++){ for (int i = 1; i <= n; i++){ fa[i][j] = fa[fa[i][j - 1]][j - 1]; } } int m; cin >> m; for (int i = 0; i < m; i++){ int u, v, c; cin >> u >> v >> c; queries[lca(u, v)].pb({u, v, c}); } solve(1, 1); cout << dp[1] << endl; }

Compilation message (stderr)

election_campaign.cpp: In function 'void solve(long long int, long long int)':
election_campaign.cpp:57:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |  for (auto [u, v, c] : queries[node]){
      |            ^
#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...