Submission #861949

#	Time	Username	Problem	Language	Result	Execution time	Memory
861949		mgl_diamond	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	149 ms	31116 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
 
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"
 
void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}
 
const int N = 1e5+5, LOG = 18;
int n, m, anc[N][LOG], st[N], en[N], cnt;
ll bit[N], sum[N], best[N];
vector<pair<ii, int>> path[N];
vector<int> graph[N];

void modify(int i, int v) {
  for(; i<=n; i+=i&-i) bit[i] += v;
}

ll query(int i) {
  ll ans = 0;
  for(; i>=1; i-=i&-i) ans += bit[i];
  return ans;
}
 
void prep(int u, int p) {
  anc[u][0] = p;
  foru(j, 1, LOG-1) anc[u][j] = anc[anc[u][j-1]][j-1];
  st[u] = ++cnt;
  fore(v, graph[u]) if (v != p) prep(v, u);
  en[u] = cnt;
}
 
bool isAnc(int u, int v) {
  return st[u] <= st[v] && en[v] <= en[u];
}
 
int lca(int u, int v) {
  if (isAnc(u, v)) return u;
  ford(j, LOG-1, 0) {
    if (!isAnc(anc[u][j], v)) {
      u = anc[u][j];
    }
  }
  return anc[u][0];
}

void dfs(int u, int p) {
  fore(v, graph[u]) if (v != p) {
    dfs(v, u);
    sum[u] += best[v];
  }
  best[u] = sum[u];

  fore(plan, path[u]) {
    int x = plan.first.first, y = plan.first.second, rew = plan.second;
    ll tmp = rew;
    if (x != u) tmp += query(st[x]);
    if (y != u) tmp += query(st[y]);
    best[u] = max(best[u], tmp + sum[u]);
  }

  // cout << u << " " << sum[u] << " " << best[u] << "\n";
  modify(st[u], sum[u] - best[u]);
  modify(en[u]+1, best[u] - sum[u]);
}
 
int main() {
  setIO();
 
  cin >> n;
 
  foru(i, 2, n) {
    int u, v;
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  
  en[0] = n+1;  
  prep(1, 0);
  
  cin >> m;
  foru(i, 1, m) {
    int u, v, w;
    cin >> u >> v >> w;
    path[lca(u, v)].push_back({{u, v}, w});
  }

  dfs(1, 0);
  cout << best[1]; 
}

Compilation message (stderr)

election_campaign.cpp: In function 'void setIO()':
election_campaign.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40