Submission #785001

#	Time	Username	Problem	Language	Result	Execution time	Memory
785001		tvladm2009	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	144 ms	30892 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = (int) 1e5 + 7;
const int K = 17;
int n;
int m;
vector<int> g[N];
int tab[K][N];
int tin[N];
int tout[N];
int depth[N];
ll sum[N];
ll dp[N];
int t = 0;

struct Offer {
  int x;
  int y;
  int cost;
};

vector<Offer> offers[N];

void dfs(int a, int p = 0) {
  tin[a] = ++t;
  depth[a] = depth[p] + 1;
  tab[0][a] = p;
  for (int k = 1; k < K; k++) {
    tab[k][a] = tab[k - 1][tab[k - 1][a]];
  }
  for (auto &b : g[a]) {
    if (b != p) {
      dfs(b, a);
    }
  }
  tout[a] = t;
}

int lca(int a, int b) {
  if (depth[a] < depth[b]) {
    swap(a, b);
  }
  for (int k = K - 1; k >= 0; k--) {
    if (depth[b] + (1 << k) <= depth[a]) {
      a = tab[k][a];
    }
  }
  if (a == b) {
    return a;
  }
  for (int k = K - 1; k >= 0; k--){
    if (tab[k][a] != tab[k][b]) {
      a = tab[k][a];
      b = tab[k][b];
    }
  }
  return tab[0][a];
}

ll aib[N];

void add(int i, int x) {
  while (i < N) {
    aib[i] += x;
    i += i & (-i);
  }
}

ll get(int i) {
  int sol = 0;
  while (i) {
    sol += aib[i];
    i -= i & (-i);
  }
  return sol;
}

void run(int a) {
  for (auto &b : g[a]) {
    if (b != tab[0][a]) {
      run(b);
      sum[a] += dp[b];
    }
  }
  dp[a] = sum[a];
  for (auto &i : offers[a]) {
    ll now = get(tin[i.x]) + get(tin[i.y]) + sum[a] + i.cost;
    dp[a] = max(dp[a], now);
  }
  add(tin[a], sum[a] - dp[a]);
  add(tout[a] + 1, dp[a] - sum[a]);
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);

  bool isHome;

  isHome = true;
  isHome = false;

  if (isHome) {
    freopen ("input", "r", stdin);
  } else {
    ios::sync_with_stdio(0); cin.tie(0);
  }

  cin >> n;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(1);
  cin >> m;
  for (int i = 1; i <= m; i++) {
    int x, y, cost;
    cin >> x >> y >> cost;
    offers[lca(x, y)].push_back({x, y, cost});
  }
  run(1);
  cout << dp[1] << "\n";
  return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:107:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |     freopen ("input", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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