oj.uz

Submission #528614

# Submission time Handle Problem Language Result Execution time Memory
528614 2022-02-20T18:57:50 Z Alex_tz307 Election Campaign (JOI15_election_campaign) C++17
10 / 100
 135 ms 30132 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 1e5;
const int kLog = 16;
int n, timer, tin[1 + kN], tout[1 + kN], depth[1 + kN], anc[1 + kN][1 + kLog];
vector<int> g[1 + kN];
vector<tuple<int, int, int>> paths[1 + kN];
int64_t ans, aib[1 + kN], sum[1 + kN];

void maxSelf(int64_t &x, int64_t y) {
  if (x < y) {
    x = y;
  }
}

void update(int64_t aib[], int x, int v) {
  for (int i = x; i <= n; i += i & -i) {
    aib[i] += v;
  }
}

int64_t query(int64_t aib[], int x) {
  int64_t ans = 0;
  for (int i = x; i > 0; i = i & (i - 1)) {
    ans += aib[i];
  }
  return ans;
}

int64_t query(int64_t aib[], int l, int r) {
  return query(aib, r) - query(aib, l);
}

void dfs1(int u) {
  tin[u] = ++timer;
  for (int i = 1; i <= kLog; ++i) {
    anc[u][i] = anc[anc[u][i - 1]][i - 1];
    if (anc[u][i] == 0) {
      break;
    }
  }
  for (int v : g[u]) {
    if (v != anc[u][0]) {
      anc[v][0] = u;
      depth[v] = depth[u] + 1;
      dfs1(v);
    }
  }
  tout[u] = timer;
}

int getLca(int u, int v) {
  if (depth[u] < depth[v]) {
    swap(u, v);
  }
  for (int i = kLog; i >= 0; --i) {
    if (depth[u] - (1 << i) >= depth[v]) {
      u = anc[u][i];
    }
  }
  if (u == v) {
    return u;
  }
  for (int i = kLog; i >= 0; --i) {
    if (anc[u][i] != anc[v][i]) {
      u = anc[u][i];
      v = anc[v][i];
    }
  }
  return anc[u][0];
}

int64_t dfs2(int u) {
  int64_t sumChildren = 0, dp = 0;
  for (int v : g[u]) {
    if (v != anc[u][0]) {
      int64_t ret = dfs2(v);
      maxSelf(dp, ret);
      sumChildren += ret;
    }
  }
  update(sum, tin[u], sumChildren);
  update(sum, tout[u] + 1, -sumChildren);
  for (auto it : paths[u]) {
    int p, q, w;
    tie(p, q, w) = it;
    maxSelf(dp, query(sum, tin[u], tin[p]) + query(sum, tin[u], tin[q]) + sumChildren + w
                - query(aib, tin[u], tin[p]) - query(aib, tin[u], tin[q]));
  }
  update(aib, tin[u], dp);
  update(aib, tout[u] + 1, -dp);
  return dp;
}

void testCase() {
  cin >> n;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  depth[1] = 1;
  dfs1(1);
  int m;
  cin >> m;
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    paths[getLca(u, v)].emplace_back(u, v, w);
  }
  cout << dfs2(1) << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5012 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Incorrect 3 ms 5068 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5000 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 5156 KB Output is correct
4 Correct 98 ms 29804 KB Output is correct
5 Correct 99 ms 29724 KB Output is correct
6 Correct 87 ms 29752 KB Output is correct
7 Correct 121 ms 29724 KB Output is correct
8 Correct 100 ms 29768 KB Output is correct
9 Correct 89 ms 29744 KB Output is correct
10 Correct 135 ms 29796 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5000 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 5156 KB Output is correct
4 Correct 98 ms 29804 KB Output is correct
5 Correct 99 ms 29724 KB Output is correct
6 Correct 87 ms 29752 KB Output is correct
7 Correct 121 ms 29724 KB Output is correct
8 Correct 100 ms 29768 KB Output is correct
9 Correct 89 ms 29744 KB Output is correct
10 Correct 135 ms 29796 KB Output is correct
11 Correct 11 ms 5916 KB Output is correct
12 Correct 109 ms 30008 KB Output is correct
13 Correct 112 ms 30020 KB Output is correct
14 Correct 100 ms 30108 KB Output is correct
15 Correct 101 ms 30020 KB Output is correct
16 Correct 96 ms 30100 KB Output is correct
17 Correct 115 ms 30008 KB Output is correct
18 Correct 106 ms 30132 KB Output is correct
19 Correct 107 ms 30116 KB Output is correct
20 Correct 107 ms 30020 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 134 ms 21496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5012 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Incorrect 3 ms 5068 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5012 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Incorrect 3 ms 5068 KB Output isn't correct
5 Halted 0 ms 0 KB -