Submission #529973

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
529973	2022-02-24T08:39:15 Z	cig32	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	138 ms	68924 KB

election_campaign

#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];
void tour(int node, int prv) {
  e.push_back(node);
  dep[node] = (prv == -1 ? 0 : dep[prv] + 1);
  par[0][node] = prv;
  for(int x: adj[node]) {
    if(x != prv) {
      tour(x, node);
      e.push_back(node);
    }
  }
}
int l[MAXN], r[MAXN];
pair<int, int> st[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(st[k][m1], st[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(st[k][m1], st[k][m2 - (1<<k) + 1]).second;
}
struct plan {
  int u, v, cost;
};
vector<plan> v[MAXN];
int s[MAXN];
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;
    }
  }
  s[node] = sum;
  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] + s[(f.u == node ? f.v : f.u)]);
      }
      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] + s[f.u] + s[f.v]);
      }
    }
  }
  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++) st[0][i] = {dep[e[i]], e[i]};
  for(int i=1; i<18; i++) {
    for(int j=1; j<e.size(); j++) {
      st[i][j] = min(st[i-1][j], st[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);
}

Compilation message

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

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5196 KB	Output is correct
2	Correct	3 ms	5196 KB	Output is correct
3	Correct	4 ms	5804 KB	Output is correct
4	Correct	123 ms	68564 KB	Output is correct
5	Correct	134 ms	68656 KB	Output is correct
6	Correct	127 ms	68564 KB	Output is correct
7	Correct	131 ms	68564 KB	Output is correct
8	Correct	133 ms	68608 KB	Output is correct
9	Correct	128 ms	68484 KB	Output is correct
10	Correct	131 ms	68472 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5196 KB	Output is correct
2	Correct	3 ms	5196 KB	Output is correct
3	Correct	4 ms	5804 KB	Output is correct
4	Correct	123 ms	68564 KB	Output is correct
5	Correct	134 ms	68656 KB	Output is correct
6	Correct	127 ms	68564 KB	Output is correct
7	Correct	131 ms	68564 KB	Output is correct
8	Correct	133 ms	68608 KB	Output is correct
9	Correct	128 ms	68484 KB	Output is correct
10	Correct	131 ms	68472 KB	Output is correct
11	Correct	11 ms	6684 KB	Output is correct
12	Correct	138 ms	68924 KB	Output is correct
13	Correct	132 ms	68836 KB	Output is correct
14	Correct	131 ms	68804 KB	Output is correct
15	Correct	138 ms	68808 KB	Output is correct
16	Correct	130 ms	68788 KB	Output is correct
17	Correct	129 ms	68832 KB	Output is correct
18	Correct	134 ms	68768 KB	Output is correct
19	Correct	134 ms	68760 KB	Output is correct
20	Correct	133 ms	68804 KB	Output is correct