oj.uz

Submission #529995

# Submission time Handle Problem Language Result Execution time Memory
529995 2022-02-24T10:10:01 Z cig32 Election Campaign (JOI15_election_campaign) C++17
10 / 100
 204 ms 71288 KB 
#include "bits/stdc++.h"
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
//#define int long long
 
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
vector<int> adj[MAXN];
int n, m;
vector<int> e;
int dep[MAXN];
int par[17][MAXN];
int pos[MAXN];
int sz[MAXN];
int nxt = 0;
void tour(int node, int prv) {
  e.push_back(node);
  dep[node] = (prv == -1 ? 0 : dep[prv] + 1);
  par[0][node] = prv;
  pos[node] = ++nxt;
  sz[node] = 1;
  for(int x: adj[node]) {
    if(x != prv) {
      tour(x, node);
      sz[node] += sz[x];
      e.push_back(node);
    }
  }
}
int l[MAXN], r[MAXN];
pair<int, int> sp[18][2*MAXN]; // euler tour
int lca_dep(int x, int y) {
  int m1 = min(l[x], l[y]);
  int m2 = max(r[x], r[y]);
  int k = 32 - __builtin_clz(m2 - m1 + 1) - 1;
  return min(sp[k][m1], sp[k][m2 - (1<<k) + 1]).first;
}
int lca_idx(int x, int y) {
  int m1 = min(l[x], l[y]);
  int m2 = max(r[x], r[y]);
  int k = 32 - __builtin_clz(m2 - m1 + 1) - 1;
  return min(sp[k][m1], sp[k][m2 - (1<<k) + 1]).second;
}
struct plan {
  int u, v, cost;
};
vector<plan> v[MAXN];
struct node {
  int upd = 0;
  int ans = 0;
} st[4*MAXN];
void u(int l, int r, int constl, int constr, int idx, int val) {
  if(l <= constl && constr <= r) {
    st[idx].upd += val;
    st[idx].ans += val;
    return;
  }
  if(st[idx].upd != 0) {
    st[2*idx+1].upd += st[idx].upd;
    st[2*idx+2].upd += st[idx].upd;
    st[2*idx+1].ans += st[idx].upd;
    st[2*idx+2].ans += st[idx].upd;
    st[idx].upd = 0;
    st[idx].ans = min(st[2*idx+1].ans, st[2*idx+2].ans);
  }
  int mid = (constl + constr) >> 1;
  if(mid < l || r < constl) u(l, r, mid+1, constr, 2*idx+2, val);
  else if(constr < l || r < mid + 1) u(l, r, constl, mid, 2*idx+1, val);
  else {
    u(l, r, constl, mid, 2*idx+1, val);
    u(l, r, mid+1, constr, 2*idx+2, val);
  }
  st[idx].ans = min(st[2*idx+1].ans, st[2*idx+2].ans);
}
int qu(int l, int r, int constl, int constr, int idx) {
  if(l <= constl && constr <= r) return st[idx].ans;
  int mid = (constl + constr) >> 1;
  if(mid < l || r < constl) return qu(l, r, mid+1, constr, 2*idx+2);
  else if(constr < l || r < mid+1) return qu(l, r, constl, mid, 2*idx+1);
  else return min(qu(l, r, constl, mid, 2*idx+1), qu(l, r, mid+1, constr, 2*idx+2));
}
void update(int l, int r, int v) {
  u(l, r, 0, MAXN-1, 0, v);
}
int query(int i) {
  return qu(pos[i], pos[i], 0, MAXN-1, 0);
}
int dpf(int node, int prv) {
  int sum = 0;
  unordered_map<int, int> contrib;
  for(int x: adj[node]) {
    if(x != prv) {
      int d = dpf(x, node);
      sum += d;
      contrib[x] = d;
    }
  }
  int ans = sum;
  if(v[node].size()) {
    for(plan f: v[node]) {
      if(f.u == node || f.v == node) {
        int dist = dep[(f.v == node ? f.u : f.v)] - dep[node] - 1;
        int cur = (f.u == node ? f.v : f.u);
        for(int k=16; k>=0; k--) {
          if(dist >= (1 << k)) {
            dist -= (1 << k);
            cur = par[k][cur];
          }
        }
        ans = max(ans, f.cost + sum - contrib[cur] + query(f.u ^ f.v ^ node));
      }
      else {
        int dist = dep[f.u] - dep[node] - 1;
        int cur = f.u;
        for(int k=16; k>=0; k--) {
          if(dist >= (1 << k)) {
            dist -= (1 << k);
            cur = par[k][cur];
          }
        }
        int dist2 = dep[f.v] - dep[node] - 1;
        int cur2 = f.v;
        for(int k=16; k>=0; k--) {
          if(dist2 >= (1 << k)) {
            dist2 -= (1 << k);
            cur2 = par[k][cur2];
          }
        }
        ans = max(ans, f.cost + sum - contrib[cur] - contrib[cur2] + query(f.u) + query(f.v));
      }
    }
  }
  for(int x: adj[node]) {
    if(x != prv) {
      update(pos[x], pos[x] + sz[x] - 1, sum - contrib[x]);
    }
  }
  update(pos[node], pos[node], sum);
  return ans;
}
void solve(int tc) {
  cin >> n;
  for(int i=1; i<n; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  e.push_back(0);
  tour(1, -1);
  for(int i=1; i<e.size(); i++) {
    if(l[e[i]] == 0) l[e[i]] = i;
    r[e[i]] = i;
  }
  for(int i=1; i<e.size(); i++) sp[0][i] = {dep[e[i]], e[i]};
  for(int i=1; i<18; i++) {
    for(int j=1; j<e.size(); j++) {
      sp[i][j] = min(sp[i-1][j], sp[i-1][j + (1<< (i-1))]);
    }
  }
  for(int i=1; i<17; i++) {
    for(int j=1; j<=n; j++) {
      par[i][j] = par[i-1][par[i-1][j]];
    }
  }
  cin >> m;
  for(int i=1; i<=m; i++) {
    int q, w, z;
    cin >> q >> w >> z;
    int j = lca_idx(q, w);
    v[j].push_back({q, w, z});
  }
  cout << dpf(1, -1) << "\n";
}
int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1;// cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
/*
9
1 2
1 3
2 4
3 7
4 5
4 6
7 8
7 9
5
6 8 1
2 3 6
5 6 6
8 9 6
3 4 2
*/

Compilation message

election_campaign.cpp: In function 'void solve(int)':
election_campaign.cpp:154:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   for(int i=1; i<e.size(); i++) {
      |                ~^~~~~~~~~
election_campaign.cpp:158:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |   for(int i=1; i<e.size(); i++) sp[0][i] = {dep[e[i]], e[i]};
      |                ~^~~~~~~~~
election_campaign.cpp:160:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     for(int j=1; j<e.size(); j++) {
      |                  ~^~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5148 KB Output is correct
2 Correct 3 ms 5272 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 4 ms 5708 KB Output is correct
5 Incorrect 130 ms 49136 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5188 KB Output is correct
2 Correct 3 ms 5324 KB Output is correct
3 Correct 4 ms 5836 KB Output is correct
4 Correct 164 ms 70984 KB Output is correct
5 Correct 163 ms 70940 KB Output is correct
6 Correct 204 ms 70964 KB Output is correct
7 Correct 165 ms 70912 KB Output is correct
8 Correct 182 ms 71092 KB Output is correct
9 Correct 195 ms 70996 KB Output is correct
10 Correct 161 ms 70984 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5188 KB Output is correct
2 Correct 3 ms 5324 KB Output is correct
3 Correct 4 ms 5836 KB Output is correct
4 Correct 164 ms 70984 KB Output is correct
5 Correct 163 ms 70940 KB Output is correct
6 Correct 204 ms 70964 KB Output is correct
7 Correct 165 ms 70912 KB Output is correct
8 Correct 182 ms 71092 KB Output is correct
9 Correct 195 ms 70996 KB Output is correct
10 Correct 161 ms 70984 KB Output is correct
11 Correct 13 ms 6560 KB Output is correct
12 Correct 189 ms 71212 KB Output is correct
13 Correct 176 ms 71288 KB Output is correct
14 Correct 179 ms 71288 KB Output is correct
15 Correct 187 ms 71228 KB Output is correct
16 Correct 173 ms 71248 KB Output is correct
17 Correct 172 ms 71220 KB Output is correct
18 Correct 184 ms 71256 KB Output is correct
19 Correct 178 ms 71240 KB Output is correct
20 Correct 194 ms 71256 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 197 ms 50844 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 5148 KB Output is correct
2 Correct 3 ms 5272 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 4 ms 5708 KB Output is correct
5 Incorrect 130 ms 49136 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5148 KB Output is correct
2 Correct 3 ms 5272 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 4 ms 5708 KB Output is correct
5 Incorrect 130 ms 49136 KB Output isn't correct
6 Halted 0 ms 0 KB -