oj.uz

Submission #729390

# Submission time Handle Problem Language Result Execution time Memory
729390 2023-04-24T02:19:08 Z jampm Election Campaign (JOI15_election_campaign) C++17
30 / 100
 1000 ms 28248 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const int Mxn = 1e5 + 1;
const int mxn = 2e5 + 1;


//hld
//nomás porq soy un mamador y es menos código hacer lca así que con binary lifting
int tin[Mxn], tout[Mxn], Sz[Mxn], head[Mxn], P[Mxn], Depth[Mxn], cnt = 1; 
vector<int> g[Mxn];
void get_sz(int node = 1, int parent = 1) {
  Sz[node] = 0; Depth[node] = Depth[parent] + 1; P[node] = parent;
  if (g[node][0] == parent) swap(g[node][0], g[node].back());
  for (auto & child : g[node]) {
    if (child == parent) continue;
    get_sz(child, node); Sz[node] += Sz[child];
    if (Sz[child] > Sz[g[node][0]]) swap(child, g[node][0]);
  }
}
void dfs_hld(int node = 1, int parent = 1) {
  tin[node] = cnt++;
  for (auto child : g[node]) {
    if (child == parent) continue;
    head[child] = (child == g[node][0]) ? head[node] : child;
    dfs_hld(child, node);
  }
  tout[node] = cnt++;
}
void init_hld() {head[1] = 1; Depth[1] = 0; get_sz(), dfs_hld();}
int LCA(int A, int B) {
  for (; head[A] != head[B]; A = P[head[A]]) {
    if (Depth[head[A]] < Depth[head[B]]) swap(A, B);
  }
  return (Depth[A] < Depth[B]) ? A : B;
}

//fenwi
struct fenwi {
  ll BIT[mxn];
  void upd(int i, ll val = 0) {
    for (; i < mxn; i += i&-i) BIT[i] += val;
  }
  ll sum(int i, ll val = 0) {
    for (; i > 0; i -= i&-i) val += BIT[i];
    return val;
  }
  ll query(int a, int b, int c) {
    return sum(tin[a]) + sum(tin[b]) - 2*sum(tin[c]);
  }

} bit[2];

//solve
struct query {int a, b, c;};
ll dp[Mxn], children_sum[Mxn];
vector<query> Q[Mxn];

void dfs(int node = 1, int parent = 1) {
  children_sum[node] = 0;
  for (auto child : g[node]) {
    if (child == parent) continue;
    dfs(child, node);
    children_sum[node] += dp[child];
  }
  dp[node] = children_sum[node];
  bit[0].upd(tin[node], children_sum[node]);
  bit[0].upd(tout[node], -children_sum[node]);
  for (auto [a, b, c] : Q[node]) {
    dp[node] = max(dp[node], bit[0].query(a, b, node) + children_sum[node] - bit[1].query(a, b, node) + c);
  }
  bit[1].upd(tin[node], dp[node]);
  bit[1].upd(tout[node],-dp[node]);
}


int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, m; cin >> n;
  for (int i = 1; i < n; i++) {
    int x, y; cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  cin >> m; init_hld();
  for (int i = 0; i < m; i++) {
    int x, y, c; cin >> x >> y >> c;
    Q[LCA(x, y)].push_back({x, y, c});
  }
  dfs();
  cout << dp[1] << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5160 KB Output is correct
5 Correct 104 ms 16408 KB Output is correct
6 Correct 46 ms 25600 KB Output is correct
7 Correct 66 ms 22472 KB Output is correct
8 Correct 60 ms 16736 KB Output is correct
9 Correct 71 ms 20556 KB Output is correct
10 Correct 73 ms 16716 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5076 KB Output is correct
2 Correct 3 ms 5044 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 91 ms 28248 KB Output is correct
5 Correct 103 ms 28032 KB Output is correct
6 Correct 113 ms 28024 KB Output is correct
7 Correct 91 ms 28012 KB Output is correct
8 Correct 91 ms 28128 KB Output is correct
9 Correct 91 ms 28012 KB Output is correct
10 Correct 95 ms 28008 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5076 KB Output is correct
2 Correct 3 ms 5044 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 91 ms 28248 KB Output is correct
5 Correct 103 ms 28032 KB Output is correct
6 Correct 113 ms 28024 KB Output is correct
7 Correct 91 ms 28012 KB Output is correct
8 Correct 91 ms 28128 KB Output is correct
9 Correct 91 ms 28012 KB Output is correct
10 Correct 95 ms 28008 KB Output is correct
11 Correct 11 ms 6100 KB Output is correct
12 Correct 96 ms 28012 KB Output is correct
13 Correct 102 ms 28120 KB Output is correct
14 Correct 95 ms 28020 KB Output is correct
15 Correct 106 ms 28112 KB Output is correct
16 Correct 88 ms 28040 KB Output is correct
17 Correct 92 ms 28104 KB Output is correct
18 Correct 91 ms 28080 KB Output is correct
19 Correct 97 ms 28132 KB Output is correct
20 Correct 88 ms 28048 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 18308 KB Output is correct
2 Correct 89 ms 28088 KB Output is correct
3 Execution timed out 1057 ms 17316 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5160 KB Output is correct
5 Correct 104 ms 16408 KB Output is correct
6 Correct 46 ms 25600 KB Output is correct
7 Correct 66 ms 22472 KB Output is correct
8 Correct 60 ms 16736 KB Output is correct
9 Correct 71 ms 20556 KB Output is correct
10 Correct 73 ms 16716 KB Output is correct
11 Correct 3 ms 5204 KB Output is correct
12 Correct 4 ms 5332 KB Output is correct
13 Correct 4 ms 5304 KB Output is correct
14 Correct 4 ms 5204 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 4 ms 5288 KB Output is correct
17 Correct 4 ms 5204 KB Output is correct
18 Correct 4 ms 5204 KB Output is correct
19 Correct 4 ms 5204 KB Output is correct
20 Correct 4 ms 5332 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5160 KB Output is correct
5 Correct 104 ms 16408 KB Output is correct
6 Correct 46 ms 25600 KB Output is correct
7 Correct 66 ms 22472 KB Output is correct
8 Correct 60 ms 16736 KB Output is correct
9 Correct 71 ms 20556 KB Output is correct
10 Correct 73 ms 16716 KB Output is correct
11 Correct 5 ms 5076 KB Output is correct
12 Correct 3 ms 5044 KB Output is correct
13 Correct 5 ms 5204 KB Output is correct
14 Correct 91 ms 28248 KB Output is correct
15 Correct 103 ms 28032 KB Output is correct
16 Correct 113 ms 28024 KB Output is correct
17 Correct 91 ms 28012 KB Output is correct
18 Correct 91 ms 28128 KB Output is correct
19 Correct 91 ms 28012 KB Output is correct
20 Correct 95 ms 28008 KB Output is correct
21 Correct 11 ms 6100 KB Output is correct
22 Correct 96 ms 28012 KB Output is correct
23 Correct 102 ms 28120 KB Output is correct
24 Correct 95 ms 28020 KB Output is correct
25 Correct 106 ms 28112 KB Output is correct
26 Correct 88 ms 28040 KB Output is correct
27 Correct 92 ms 28104 KB Output is correct
28 Correct 91 ms 28080 KB Output is correct
29 Correct 97 ms 28132 KB Output is correct
30 Correct 88 ms 28048 KB Output is correct
31 Correct 159 ms 18308 KB Output is correct
32 Correct 89 ms 28088 KB Output is correct
33 Execution timed out 1057 ms 17316 KB Time limit exceeded
34 Halted 0 ms 0 KB -