Submission #439149

#	Time	Username	Problem	Language	Result	Execution time	Memory
439149		peijar	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	562 ms	44356 KiB

election_campaign

#include <bits/stdc++.h>
#define int long long
using namespace std;

template <class T> class Fenwick {
public:
  int lim;
  vector<T> bit;

  Fenwick(int n) : lim(n + 1), bit(lim) {}

  void upd(int pos, T val) {
    for (pos++; pos < lim; pos += pos & -pos)
      bit[pos] += val;
  }

  T sum(int r) { // < r
    T ret = 0;
    for (; r; r -= r & -r)
      ret += bit[r];
    return ret;
  }

  T sum(int l, int r) { // [l, r)
    return sum(r) - sum(l);
  }
};

struct Voyage {
  int u, v, gain;
};

const int MAXN = 1e5;
const int MAXP = 17;

int par[MAXP][MAXN];
vector<int> adj[MAXN];
vector<Voyage> voyages[MAXN];
int depth[MAXN];
int timeIn[MAXN], timeOut[MAXN];
int curTime = 0;
int nbSommets, nbVoyages;
Fenwick<int> fen(0);

int dpAvec[MAXN], dpSans[MAXN];

int goUp(int u, int d) {
  for (int p = 0; p < MAXP; ++p)
    if ((1 << p) & d)
      u = par[p][u];
  return u;
}

int lca(int u, int v) {
  if (depth[u] < depth[v])
    swap(u, v);
  u = goUp(u, depth[u] - depth[v]);
  if (u == v)
    return u;
  for (int p = MAXP - 1; p >= 0; --p)
    if (par[p][u] != par[p][v])
      u = par[p][u], v = par[p][v];
  return par[0][u];
}

void dfs(int u, int p) {
  timeIn[u] = curTime++;
  for (auto v : adj[u])
    if (v != p) {
      depth[v] = depth[u] + 1;
      par[0][v] = u;
      dfs(v, u);
    }
  timeOut[u] = curTime++;
}

void subAdd(int iSommet, int x) {
  fen.upd(timeIn[iSommet], x);
  fen.upd(timeOut[iSommet] + 1, -x);
}

int pointQuery(int iSommet) { return fen.sum(timeIn[iSommet] + 1); }

void dfs2(int u) {
  for (auto v : adj[u]) {
    if (v == par[0][u])
      continue;
    dfs2(v);
    dpSans[u] += dpAvec[v];
  }
  dpAvec[u] = dpSans[u];
  for (auto voyage : voyages[u]) {
    int f1 = voyage.u, f2 = voyage.v;
    int solAvec = voyage.gain;
    if (f1 != u) {
      int p = goUp(f1, depth[f1] - depth[u] - 1);
      solAvec += pointQuery(f1) + dpSans[f1] - dpAvec[p];
    }
    if (f2 != u) {
      int p = goUp(f2, depth[f2] - depth[u] - 1);
      solAvec += pointQuery(f2) + dpSans[f2] - dpAvec[p];
    }
    solAvec += dpSans[u];
    dpAvec[u] = max(dpAvec[u], solAvec);
  }

  for (auto v : adj[u])
    if (v != par[0][u])
      subAdd(v, dpSans[u] - dpAvec[v]);
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> nbSommets;
  for (int i = 1; i < nbSommets; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(0, 0);
  for (int p = 0; p < MAXP - 1; ++p)
    for (int i = 0; i < nbSommets; ++i)
      par[p + 1][i] = par[p][par[p][i]];

  fen = Fenwick<int>(curTime);
  cin >> nbVoyages;
  for (int iVoyage = 0; iVoyage < nbVoyages; ++iVoyage) {
    int u, v, c;
    cin >> u >> v >> c;
    --u, --v;
    int l = lca(u, v);
    voyages[l].push_back({u, v, c});
  }
  dfs2(0);
  cout << dpAvec[0] << endl;
}

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