Submission #565311

#	Time	Username	Problem	Language	Result	Execution time	Memory
565311		SSRS	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	234 ms	25808 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
struct binary_indexed_tree{
  int N;
  vector<int> BIT;
  binary_indexed_tree(){
  }
  binary_indexed_tree(int N): N(N), BIT(N + 1, 0){
  }
  void add(int i, int x){
    i++;
    while (i <= N){
      BIT[i] += x;
      i += i & -i;
    }
  }
  int sum(int i){
    int ans = 0;
    while (i > 0){
      ans += BIT[i];
      i -= i & -i;
    }
    return ans;
  }
  int sum(int L, int R){
    return sum(R) - sum(L);
  }
};
struct heavy_light_decomposition{
  vector<int> p, sz, in, next;
  binary_indexed_tree BIT;
  heavy_light_decomposition(vector<int> &p, vector<vector<int>> &c): p(p){
    int N = p.size();
    sz = vector<int>(N, 1);
    dfs1(c);
    in = vector<int>(N);
    next = vector<int>(N, 0);
    int t = 0;
    dfs2(c, t);
    BIT = binary_indexed_tree(N);
  }
  void dfs1(vector<vector<int>> &c, int v = 0){
    for (int &w : c[v]){
      dfs1(c, w);
      sz[v] += sz[w];
      if (sz[w] > sz[c[v][0]]){
        swap(w, c[v][0]);
      }
    }
  }
  void dfs2(vector<vector<int>> &c, int &t, int v = 0){
    in[v] = t;
    t++;
    for (int w : c[v]){
      if (w == c[v][0]){
        next[w] = next[v];
      } else {
        next[w] = w;
      }
      dfs2(c, t, w);
    }
  }
  int lca(int u, int v){
    while (true){
      if (in[u] > in[v]){
        swap(u, v);
      }
      if (next[u] == next[v]){
        return u;
      }
      v = p[next[v]];
    }
  }
  void add(int v, int x){
    BIT.add(in[v], x);
  }
  int path_sum(int u, int v){
    int w = lca(u, v);
    int ans = 0;
    while (next[u] != next[w]){
      ans += BIT.sum(in[next[u]], in[u] + 1);
      u = p[next[u]];
    }
    ans += BIT.sum(in[w], in[u] + 1);
    while (next[v] != next[w]){
      ans += BIT.sum(in[next[v]], in[v] + 1);
      v = p[next[v]];
    }
    ans += BIT.sum(in[w] + 1, in[v] + 1);
    return ans;
  }
};
int main(){
  int N;
  cin >> N;
  vector<vector<int>> E(N);
  for (int i = 0; i < N - 1; i++){
    int X, Y;
    cin >> X >> Y;
    X--;
    Y--;
    E[X].push_back(Y);
    E[Y].push_back(X);
  }
  int M;
  cin >> M;
  vector<int> A(M), B(M), C(M);
  for (int i = 0; i < M; i++){
    cin >> A[i] >> B[i] >> C[i];
    A[i]--;
    B[i]--;
  }
  vector<int> p(N, -1);
  vector<vector<int>> c(N);
  queue<int> Q;
  Q.push(0);
  vector<int> bfs;
  while (!Q.empty()){
    int v = Q.front();
    Q.pop();
    bfs.push_back(v);
    for (int w : E[v]){
      if (w != p[v]){
        p[w] = v;
        c[v].push_back(w);
        Q.push(w);
      }
    }
  }
  heavy_light_decomposition T(p, c);
  vector<vector<int>> id(N);
  for (int i = 0; i < M; i++){
    id[T.lca(A[i], B[i])].push_back(i);
  }
  reverse(bfs.begin(), bfs.end());
  vector<int> dp(N, 0);
  vector<int> dpsum(N, 0);
  for (int v : bfs){
    for (int w : c[v]){
      dpsum[v] += dp[w];
    }
    T.add(v, dpsum[v]);
    int mx = dpsum[v];
    for (int w : id[v]){
      mx = max(mx, T.path_sum(A[w], B[w]) + C[w]);
    }
    dp[v] = mx;
    T.add(v, -dp[v]);
  }
  cout << dp[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