Submission #112737

#	Time	Username	Problem	Language	Result	Execution time	Memory
112737		Yehezkiel	Election Campaign (JOI15_election_campaign)	C++11	100 / 100	302 ms	38520 KiB

election_campaign

//#include "campaign.h"
#include <bits/stdc++.h>
using namespace std;

#define psb push_back
#define fi first
#define se second
#define eb emplace_back
typedef pair<int,int> PII;

const int MAXN = 100000;
int n, m;
vector <int> node[MAXN + 5];

void moveToGlobal(int N, int M, const vector <int> &U, const vector <int> &V) {
  n = N;
  m = M;
  for (int i = 0; i < n - 1; ++i) {
    node[U[i]].psb(V[i]);
    node[V[i]].psb(U[i]);
  }
}

const int logN = 17;
int par[logN + 5][MAXN + 5] = {};
int depth[MAXN + 5];
void setUpLCA(int now, int _par = 0, int _depth = 0) {
  par[0][now] = _par;
  depth[now] = _depth;

  for (auto v: node[now]) {
    if (v == par[0][now]) {
      continue;
    }

    setUpLCA(v, now, _depth + 1);
  }
}

void setUpLCA() {
  setUpLCA(1);

  for (int i = 1; i < logN; ++i) {
    for (int j = 1; j <= n; ++j) {
      par[i][j] = par[i - 1][par[i - 1][j]];
    }
  }
}

int LCA(int u, int v) {
  if (depth[u] > depth[v])  swap(u, v);
  int diff = depth[v] - depth[u];
  for (int i = 0; i < logN; ++i) {
    if (diff & (1 << i))
      v = par[i][v];
  }

  assert(depth[u] == depth[v]);
  if (u == v) return u;

  for (int i = logN - 1; i >= 0; --i) {
    if (par[i][u] == par[i][v]) continue;
    u = par[i][u], v = par[i][v];
  }

  assert(par[0][u] == par[0][v]);
  return par[0][u];
}

class treeNode {
public:
  int fi, se;
  int fiLazy, seLazy;
  bool lazy;

  treeNode() {
    fi = se = fiLazy = seLazy = 0;
    lazy = false;
  }

  treeNode operator + (const treeNode &other) {
    treeNode ret;
    ret.fi = fi + other.fi;
    ret.se = se + other.se;
    return ret;
  }

  void apply(int newFi, int newSe) {
    fiLazy += newFi;
    fi += newFi;
    seLazy += newSe;
    se += newSe;
    lazy = true;
  }

  PII toPair() {
    return make_pair(fi, se);
  }
};

class Segtree {
public:
  static const int treeSize = 131072;
  treeNode tree[treeSize * 2 + 5];

  void pushDown(int idx) {
    if (!tree[idx].lazy)  return;

    tree[idx << 1].apply(tree[idx].fiLazy, tree[idx].seLazy);
    tree[(idx << 1) | 1].apply(tree[idx].fiLazy, tree[idx].seLazy);
    tree[idx].fiLazy = tree[idx].seLazy = 0;
    tree[idx].lazy = false;
  }

  void pullUp(int idx) {
    tree[idx] = tree[idx << 1] + tree[(idx << 1) | 1];
  }

  int l, r, newFi, newSe;

  void update(int left, int right, int idx) {
    if (l <= left && right <= r) {
      tree[idx].apply(newFi, newSe);
      return;
    }

    if (l > right || r < left) {
      return;
    }

    pushDown(idx);
    int mid = (left + right) >> 1;
    update(left, mid, idx << 1);
    update(mid + 1, right, (idx << 1) | 1);
    pullUp(idx);
  }

  void update(int _l, int _r, int _newFi, int _newSe) {
    l = _l; r = _r; newFi = _newFi; newSe = _newSe;
    update(1, n, 1);
  }

  PII combine(PII a, PII b) {
    return make_pair(a.fi + b.fi, a.se + b.se);
  }

  int target;
  PII query(int left, int right, int idx) {
    if (left == right) {
      assert(left == target);
      return tree[idx].toPair();
    }

    pushDown(idx);
    int mid = (left + right) >> 1;
    if (target <= mid)
      return query(left, mid, idx << 1);
    else
      return query(mid + 1, right, (idx << 1) | 1);
  }

  PII query(int _target) {
    target = _target;
    return query(1, n, 1);
  }
}segtree;

class query{
public:
  int u, v, val;
  query(int _u, int _v, int _val) : u(_u), v(_v), val(_val) {}
};
vector <query> queries[MAXN + 5];

void fillQueries(const vector <int> &A, const vector <int> &B, const vector <int> &C) {
  for (int i = 0; i < m; ++i) {
    int temp = LCA(A[i], B[i]);
    queries[temp].eb(A[i], B[i], C[i]);
  }
}

int rangeL[MAXN + 5];
int rangeR[MAXN + 5];
int counter = 0;
void fillRange(int now) {
  rangeL[now] = ++counter;  
  for (auto v: node[now]) {
    if (v == par[0][now])
      continue;
    fillRange(v);
  }
  rangeR[now] = counter;
}
void fillRange() {
  fillRange(1);
}

int dp[2][MAXN + 5] = {};
int findOptimum(int sub, int root) {
  assert(sub != root);
  assert(depth[sub] > depth[root]);
  PII temp = segtree.query(rangeL[sub]);
  return temp.se - temp.fi + dp[1][root];
}
void fillDp(int now) {
  dp[0][now] = dp[1][now] = 0;
  for (auto v: node[now]) {
    if (v == par[0][now]) {
      continue;
    }

    fillDp(v);
    dp[1][now] += dp[0][v];
  }

  for (auto q: queries[now]) {
    if (now == q.v) swap(q.u, q.v);
    int candidate = q.val;
    if (q.u == now) {
      candidate += findOptimum(q.v, now);
    } else {
      candidate += findOptimum(q.u, now);
      candidate += findOptimum(q.v, now);
      candidate -= dp[1][now];
    }
    dp[0][now] = max(dp[0][now], candidate);
  }
  dp[0][now] = max(dp[0][now], dp[1][now]);

  segtree.update(rangeL[now], rangeR[now], dp[0][now], dp[1][now]);
}
void fillDp() {
  fillDp(1);
}

int getMaximumVotes(int N, int M, vector<int> U, vector<int> V,
                    vector<int> A, vector<int> B, vector<int> C) {
  moveToGlobal(N, M, U, V);
  setUpLCA();
  fillQueries(A, B, C);
  fillRange();
  fillDp();
  return dp[0][1];
}

int main() {
  int N, M;
  vector<int> U, V;
  vector<int> A, B, C;

  scanf("%d", &N);
  U.resize(N-1); V.resize(N-1);

  for (int i = 0 ; i < N-1 ; i++) {
    scanf("%d %d", &U[i], &V[i]);
  }

  scanf("%d", &M);
  A.resize(M); B.resize(M); C.resize(M);
  for (int i = 0 ; i < M ; i++) {
    scanf("%d %d %d", &A[i], &B[i], &C[i]);
  }

  int ans = getMaximumVotes(N, M, U, V, A, B, C);
  printf("%d\n", ans);
  
  return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:251:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:255:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &U[i], &V[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:258:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &M);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:261:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &A[i], &B[i], &C[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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