Submission #361970

#	Time	Username	Problem	Language	Result	Execution time	Memory
361970		AlexLuchianov	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	266 ms	36504 KiB

election_campaign

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
int const lgmax = 20;
std::vector<int> g[1 + nmax];
int far[1 + lgmax][1 + nmax], level[1 + nmax];
int start[1 + nmax], stop[1 + nmax], ptr = 0;

void dfs(int node, int parent) {
  far[0][node] = parent;
  level[node] = level[parent] + 1;
  start[node] = ++ptr;

  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h];
    if(to != parent)
      dfs(to, node);
  }
  stop[node] = ptr;
}

int getlca(int x, int y) {
  if(level[x] < level[y])
    std::swap(x, y);
  for(int h = lgmax; 0 <= h; h--)
    if(level[y] + (1 << h) <= level[x])
      x = far[h][x];
  if(x == y)
    return x;
  for(int h = lgmax; 0 <= h; h--)
    if(far[h][x] != far[h][y]) {
      x = far[h][x];
      y = far[h][y];
    }
  return far[0][x];
}

class FenwickTree{
private:
  std::vector<ll> aib;
  int n;
public:
  FenwickTree(int n_) {
    n = n_;
    aib.resize(1 + 4 * n);
  }
  void update(int pos, ll val) {
    for(int x = pos; x <= n; x += (x ^ (x & (x - 1))))
      aib[x] += val;
  }
  ll query(int pos) {
    ll result = 0;
    for(int x = pos; 0 < x; x = (x & (x - 1)))
      result += aib[x];
    return result;
  }
};

ll dp[1 + nmax], sum[1 + nmax];

struct Event{
  int x;
  int y;
  int cost;
};
std::vector<Event> events[1 + nmax];

void solve(int node, int parent, FenwickTree &aib) {
  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h];
    if(to != parent) {
      solve(to, node, aib);
      sum[node] += dp[to];
    }
  }
  for(int h = 0; h < events[node].size(); h++) {
    Event e = events[node][h];
    ll result = aib.query(start[e.x]) + aib.query(start[e.y]) + e.cost + sum[node];
    dp[node] = std::max(dp[node], result);
  }
  dp[node] = std::max(dp[node], sum[node]);

  aib.update(start[node], sum[node] - dp[node]);
  aib.update(stop[node] + 1, -(sum[node] - dp[node]));
}

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

  int n;
  std::cin >> n;
  for(int i = 1;i < n; i++) {
    int x, y;
    std::cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(1, 0);
  
  for(int h = 1; h <= lgmax; h++)
    for(int i = 1;i <= n; i++)
      far[h][i] = far[h - 1][far[h - 1][i]];

  int m;
  std::cin >> m;
  for(int i = 1;i <= m; i++) {
    int x, y, cost;
    std::cin >> x >> y >> cost;
    events[getlca(x, y)].push_back({x, y, cost});
  }

  FenwickTree aib(1 + n);
  solve(1, 0, aib);
  std::cout << dp[1];

  return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~
election_campaign.cpp: In function 'void solve(int, int, FenwickTree&)':
election_campaign.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~
election_campaign.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for(int h = 0; h < events[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~

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