Submission #132701

#	Time	Username	Problem	Language	Result	Execution time	Memory
132701		Just_Solve_The_Problem	Election Campaign (JOI15_election_campaign)	C++11	100 / 100	291 ms	31268 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e5 + 7;

vector <int> gr[N];
int n, m;
vector <tuple<int, int, int>> vec;
int tin[N], tout[N], lc[17][N], sz[N];
int tiktak;
vector <int> query[N];

void dfs(int v, int pr) {
  tin[v] = ++tiktak;
  lc[0][v] = pr;
  for (int i = 1; i < 17; i++) {
    lc[i][v] = lc[i - 1][lc[i - 1][v]];
  }
  sz[v] = 1;
  for (int to : gr[v]) {
    if (to == pr) continue;
    dfs(to, v);
    sz[v] += sz[to];
  }
  tout[v] = ++tiktak;
}

bool upper(int a, int b) {
  return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
  if (upper(a, b)) return a;
  if (upper(b, a)) return b;
  for (int i = 16; i >= 0; i--) {
    if (!upper(lc[i][a], b)) a = lc[i][a];
  }
  return lc[0][a];
}

struct fen {
  int tree[N + N];
  fen() {
    memset(tree, 0, sizeof tree);
  }
  void upd(int pos, int val) {
    while (pos < N + N) {
      tree[pos] += val;
      pos = pos | pos + 1;
    }
  }
  int get(int r) {
    int res = 0;
    while (r >= 0) {
      res += tree[r];
      r = (r & r + 1) - 1;
    }
    return res;
  }
  int get(int l, int r) {
    if (l > r) return 0;
    return get(r) - get(l - 1);
  }
};
fen tr, tr1;

int dp[N], dp1[N];

void dfs1(int v, int pr) {
  for (int to : gr[v]) {
    if (to == pr) continue;
    dfs1(to, v);
    dp1[v] += dp[to];
  }
  dp[v] = dp1[v];
  for (int id : query[v]) {
    int a, b;
    tie(a, b) = make_tuple(get<0>(vec[id]), get<1>(vec[id]));
    dp[v] = max(dp[v], dp1[v] + tr1.get(tin[v], tin[a]) + tr1.get(tin[v], tin[b]) - tr.get(tin[v], tin[a]) - tr.get(tin[v], tin[b]) + get<2>(vec[id]));
  }
  tr1.upd(tin[v], dp1[v]);
  tr1.upd(tout[v], -dp1[v]);
  tr.upd(tin[v], dp[v]);
  tr.upd(tout[v], -dp[v]);
}

main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    gr[u].push_back(v);
    gr[v].push_back(u);
  }
  dfs(1, 1);
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    if (tin[u] > tin[v]) swap(u, v);
    vec.push_back({u, v, w});
    query[lca(u, v)].push_back(i);
  }
  dfs1(1, 1);
  printf("%d\n", dp[1]);
}

Compilation message (stderr)

election_campaign.cpp: In member function 'void fen::upd(int, int)':
election_campaign.cpp:50:23: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
       pos = pos | pos + 1;
                   ~~~~^~~
election_campaign.cpp: In member function 'int fen::get(int)':
election_campaign.cpp:57:18: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
       r = (r & r + 1) - 1;
                ~~^~~
election_campaign.cpp: At global scope:
election_campaign.cpp:88:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &u, &v);
     ~~~~~^~~~~~~~~~~~~~~~~
election_campaign.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &m);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &u, &v, &w);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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