Submission #112737

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
112737	2019-05-21T17:07:54 Z	Yehezkiel	Election Campaign (JOI15_election_campaign)	C++11	100 / 100	302 ms	38520 KB

election_campaign

//#include "campaign.h"
#include <bits/stdc++.h>
using namespace std;

#define psb push_back
#define fi first
#define se second
#define eb emplace_back
typedef pair<int,int> PII;

const int MAXN = 100000;
int n, m;
vector <int> node[MAXN + 5];

void moveToGlobal(int N, int M, const vector <int> &U, const vector <int> &V) {
  n = N;
  m = M;
  for (int i = 0; i < n - 1; ++i) {
    node[U[i]].psb(V[i]);
    node[V[i]].psb(U[i]);
  }
}

const int logN = 17;
int par[logN + 5][MAXN + 5] = {};
int depth[MAXN + 5];
void setUpLCA(int now, int _par = 0, int _depth = 0) {
  par[0][now] = _par;
  depth[now] = _depth;

  for (auto v: node[now]) {
    if (v == par[0][now]) {
      continue;
    }

    setUpLCA(v, now, _depth + 1);
  }
}

void setUpLCA() {
  setUpLCA(1);

  for (int i = 1; i < logN; ++i) {
    for (int j = 1; j <= n; ++j) {
      par[i][j] = par[i - 1][par[i - 1][j]];
    }
  }
}

int LCA(int u, int v) {
  if (depth[u] > depth[v])  swap(u, v);
  int diff = depth[v] - depth[u];
  for (int i = 0; i < logN; ++i) {
    if (diff & (1 << i))
      v = par[i][v];
  }

  assert(depth[u] == depth[v]);
  if (u == v) return u;

  for (int i = logN - 1; i >= 0; --i) {
    if (par[i][u] == par[i][v]) continue;
    u = par[i][u], v = par[i][v];
  }

  assert(par[0][u] == par[0][v]);
  return par[0][u];
}

class treeNode {
public:
  int fi, se;
  int fiLazy, seLazy;
  bool lazy;

  treeNode() {
    fi = se = fiLazy = seLazy = 0;
    lazy = false;
  }

  treeNode operator + (const treeNode &other) {
    treeNode ret;
    ret.fi = fi + other.fi;
    ret.se = se + other.se;
    return ret;
  }

  void apply(int newFi, int newSe) {
    fiLazy += newFi;
    fi += newFi;
    seLazy += newSe;
    se += newSe;
    lazy = true;
  }

  PII toPair() {
    return make_pair(fi, se);
  }
};

class Segtree {
public:
  static const int treeSize = 131072;
  treeNode tree[treeSize * 2 + 5];

  void pushDown(int idx) {
    if (!tree[idx].lazy)  return;

    tree[idx << 1].apply(tree[idx].fiLazy, tree[idx].seLazy);
    tree[(idx << 1) | 1].apply(tree[idx].fiLazy, tree[idx].seLazy);
    tree[idx].fiLazy = tree[idx].seLazy = 0;
    tree[idx].lazy = false;
  }

  void pullUp(int idx) {
    tree[idx] = tree[idx << 1] + tree[(idx << 1) | 1];
  }

  int l, r, newFi, newSe;

  void update(int left, int right, int idx) {
    if (l <= left && right <= r) {
      tree[idx].apply(newFi, newSe);
      return;
    }

    if (l > right || r < left) {
      return;
    }

    pushDown(idx);
    int mid = (left + right) >> 1;
    update(left, mid, idx << 1);
    update(mid + 1, right, (idx << 1) | 1);
    pullUp(idx);
  }

  void update(int _l, int _r, int _newFi, int _newSe) {
    l = _l; r = _r; newFi = _newFi; newSe = _newSe;
    update(1, n, 1);
  }

  PII combine(PII a, PII b) {
    return make_pair(a.fi + b.fi, a.se + b.se);
  }

  int target;
  PII query(int left, int right, int idx) {
    if (left == right) {
      assert(left == target);
      return tree[idx].toPair();
    }

    pushDown(idx);
    int mid = (left + right) >> 1;
    if (target <= mid)
      return query(left, mid, idx << 1);
    else
      return query(mid + 1, right, (idx << 1) | 1);
  }

  PII query(int _target) {
    target = _target;
    return query(1, n, 1);
  }
}segtree;

class query{
public:
  int u, v, val;
  query(int _u, int _v, int _val) : u(_u), v(_v), val(_val) {}
};
vector <query> queries[MAXN + 5];

void fillQueries(const vector <int> &A, const vector <int> &B, const vector <int> &C) {
  for (int i = 0; i < m; ++i) {
    int temp = LCA(A[i], B[i]);
    queries[temp].eb(A[i], B[i], C[i]);
  }
}

int rangeL[MAXN + 5];
int rangeR[MAXN + 5];
int counter = 0;
void fillRange(int now) {
  rangeL[now] = ++counter;  
  for (auto v: node[now]) {
    if (v == par[0][now])
      continue;
    fillRange(v);
  }
  rangeR[now] = counter;
}
void fillRange() {
  fillRange(1);
}

int dp[2][MAXN + 5] = {};
int findOptimum(int sub, int root) {
  assert(sub != root);
  assert(depth[sub] > depth[root]);
  PII temp = segtree.query(rangeL[sub]);
  return temp.se - temp.fi + dp[1][root];
}
void fillDp(int now) {
  dp[0][now] = dp[1][now] = 0;
  for (auto v: node[now]) {
    if (v == par[0][now]) {
      continue;
    }

    fillDp(v);
    dp[1][now] += dp[0][v];
  }

  for (auto q: queries[now]) {
    if (now == q.v) swap(q.u, q.v);
    int candidate = q.val;
    if (q.u == now) {
      candidate += findOptimum(q.v, now);
    } else {
      candidate += findOptimum(q.u, now);
      candidate += findOptimum(q.v, now);
      candidate -= dp[1][now];
    }
    dp[0][now] = max(dp[0][now], candidate);
  }
  dp[0][now] = max(dp[0][now], dp[1][now]);

  segtree.update(rangeL[now], rangeR[now], dp[0][now], dp[1][now]);
}
void fillDp() {
  fillDp(1);
}

int getMaximumVotes(int N, int M, vector<int> U, vector<int> V,
                    vector<int> A, vector<int> B, vector<int> C) {
  moveToGlobal(N, M, U, V);
  setUpLCA();
  fillQueries(A, B, C);
  fillRange();
  fillDp();
  return dp[0][1];
}

int main() {
  int N, M;
  vector<int> U, V;
  vector<int> A, B, C;

  scanf("%d", &N);
  U.resize(N-1); V.resize(N-1);

  for (int i = 0 ; i < N-1 ; i++) {
    scanf("%d %d", &U[i], &V[i]);
  }

  scanf("%d", &M);
  A.resize(M); B.resize(M); C.resize(M);
  for (int i = 0 ; i < M ; i++) {
    scanf("%d %d %d", &A[i], &B[i], &C[i]);
  }

  int ans = getMaximumVotes(N, M, U, V, A, B, C);
  printf("%d\n", ans);
  
  return 0;
}

Compilation message

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:251:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:255:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &U[i], &V[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:258:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &M);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:261:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &A[i], &B[i], &C[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	10240 KB	Output is correct
2	Correct	10 ms	10240 KB	Output is correct
3	Correct	9 ms	10240 KB	Output is correct
4	Correct	10 ms	10368 KB	Output is correct
5	Correct	132 ms	24824 KB	Output is correct
6	Correct	66 ms	32504 KB	Output is correct
7	Correct	127 ms	29816 KB	Output is correct
8	Correct	102 ms	25208 KB	Output is correct
9	Correct	141 ms	28268 KB	Output is correct
10	Correct	119 ms	25208 KB	Output is correct

Subtask #2

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	10240 KB	Output is correct
2	Correct	10 ms	10240 KB	Output is correct
3	Correct	11 ms	10496 KB	Output is correct
4	Correct	146 ms	38136 KB	Output is correct
5	Correct	154 ms	38316 KB	Output is correct
6	Correct	142 ms	38136 KB	Output is correct
7	Correct	165 ms	38136 KB	Output is correct
8	Correct	156 ms	38136 KB	Output is correct
9	Correct	138 ms	38124 KB	Output is correct
10	Correct	155 ms	38136 KB	Output is correct

Subtask #3

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	10240 KB	Output is correct
2	Correct	10 ms	10240 KB	Output is correct
3	Correct	11 ms	10496 KB	Output is correct
4	Correct	146 ms	38136 KB	Output is correct
5	Correct	154 ms	38316 KB	Output is correct
6	Correct	142 ms	38136 KB	Output is correct
7	Correct	165 ms	38136 KB	Output is correct
8	Correct	156 ms	38136 KB	Output is correct
9	Correct	138 ms	38124 KB	Output is correct
10	Correct	155 ms	38136 KB	Output is correct
11	Correct	22 ms	11808 KB	Output is correct
12	Correct	160 ms	38448 KB	Output is correct
13	Correct	157 ms	38392 KB	Output is correct
14	Correct	153 ms	38412 KB	Output is correct
15	Correct	169 ms	38444 KB	Output is correct
16	Correct	162 ms	38492 KB	Output is correct
17	Correct	168 ms	38364 KB	Output is correct
18	Correct	160 ms	38480 KB	Output is correct
19	Correct	150 ms	38392 KB	Output is correct
20	Correct	163 ms	38520 KB	Output is correct

Subtask #4

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	247 ms	29980 KB	Output is correct
2	Correct	141 ms	38136 KB	Output is correct
3	Correct	289 ms	35048 KB	Output is correct
4	Correct	172 ms	30384 KB	Output is correct
5	Correct	288 ms	34588 KB	Output is correct
6	Correct	180 ms	30572 KB	Output is correct
7	Correct	264 ms	34200 KB	Output is correct
8	Correct	221 ms	30328 KB	Output is correct
9	Correct	130 ms	38136 KB	Output is correct
10	Correct	294 ms	33328 KB	Output is correct

Subtask #5

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	10240 KB	Output is correct
2	Correct	10 ms	10240 KB	Output is correct
3	Correct	9 ms	10240 KB	Output is correct
4	Correct	10 ms	10368 KB	Output is correct
5	Correct	132 ms	24824 KB	Output is correct
6	Correct	66 ms	32504 KB	Output is correct
7	Correct	127 ms	29816 KB	Output is correct
8	Correct	102 ms	25208 KB	Output is correct
9	Correct	141 ms	28268 KB	Output is correct
10	Correct	119 ms	25208 KB	Output is correct
11	Correct	11 ms	10496 KB	Output is correct
12	Correct	11 ms	10496 KB	Output is correct
13	Correct	12 ms	10496 KB	Output is correct
14	Correct	12 ms	10496 KB	Output is correct
15	Correct	12 ms	10496 KB	Output is correct
16	Correct	12 ms	10496 KB	Output is correct
17	Correct	11 ms	10496 KB	Output is correct
18	Correct	11 ms	10464 KB	Output is correct
19	Correct	12 ms	10496 KB	Output is correct
20	Correct	11 ms	10512 KB	Output is correct

Subtask #6

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	10240 KB	Output is correct
2	Correct	10 ms	10240 KB	Output is correct
3	Correct	9 ms	10240 KB	Output is correct
4	Correct	10 ms	10368 KB	Output is correct
5	Correct	132 ms	24824 KB	Output is correct
6	Correct	66 ms	32504 KB	Output is correct
7	Correct	127 ms	29816 KB	Output is correct
8	Correct	102 ms	25208 KB	Output is correct
9	Correct	141 ms	28268 KB	Output is correct
10	Correct	119 ms	25208 KB	Output is correct
11	Correct	10 ms	10240 KB	Output is correct
12	Correct	10 ms	10240 KB	Output is correct
13	Correct	11 ms	10496 KB	Output is correct
14	Correct	146 ms	38136 KB	Output is correct
15	Correct	154 ms	38316 KB	Output is correct
16	Correct	142 ms	38136 KB	Output is correct
17	Correct	165 ms	38136 KB	Output is correct
18	Correct	156 ms	38136 KB	Output is correct
19	Correct	138 ms	38124 KB	Output is correct
20	Correct	155 ms	38136 KB	Output is correct
21	Correct	22 ms	11808 KB	Output is correct
22	Correct	160 ms	38448 KB	Output is correct
23	Correct	157 ms	38392 KB	Output is correct
24	Correct	153 ms	38412 KB	Output is correct
25	Correct	169 ms	38444 KB	Output is correct
26	Correct	162 ms	38492 KB	Output is correct
27	Correct	168 ms	38364 KB	Output is correct
28	Correct	160 ms	38480 KB	Output is correct
29	Correct	150 ms	38392 KB	Output is correct
30	Correct	163 ms	38520 KB	Output is correct
31	Correct	247 ms	29980 KB	Output is correct
32	Correct	141 ms	38136 KB	Output is correct
33	Correct	289 ms	35048 KB	Output is correct
34	Correct	172 ms	30384 KB	Output is correct
35	Correct	288 ms	34588 KB	Output is correct
36	Correct	180 ms	30572 KB	Output is correct
37	Correct	264 ms	34200 KB	Output is correct
38	Correct	221 ms	30328 KB	Output is correct
39	Correct	130 ms	38136 KB	Output is correct
40	Correct	294 ms	33328 KB	Output is correct
41	Correct	11 ms	10496 KB	Output is correct
42	Correct	11 ms	10496 KB	Output is correct
43	Correct	12 ms	10496 KB	Output is correct
44	Correct	12 ms	10496 KB	Output is correct
45	Correct	12 ms	10496 KB	Output is correct
46	Correct	12 ms	10496 KB	Output is correct
47	Correct	11 ms	10496 KB	Output is correct
48	Correct	11 ms	10464 KB	Output is correct
49	Correct	12 ms	10496 KB	Output is correct
50	Correct	11 ms	10512 KB	Output is correct
51	Correct	229 ms	30592 KB	Output is correct
52	Correct	171 ms	38392 KB	Output is correct
53	Correct	289 ms	33756 KB	Output is correct
54	Correct	165 ms	30744 KB	Output is correct
55	Correct	245 ms	30260 KB	Output is correct
56	Correct	153 ms	38516 KB	Output is correct
57	Correct	226 ms	34484 KB	Output is correct
58	Correct	174 ms	30512 KB	Output is correct
59	Correct	210 ms	30604 KB	Output is correct
60	Correct	145 ms	38392 KB	Output is correct
61	Correct	218 ms	34680 KB	Output is correct
62	Correct	180 ms	30288 KB	Output is correct
63	Correct	247 ms	30064 KB	Output is correct
64	Correct	160 ms	38392 KB	Output is correct
65	Correct	302 ms	34288 KB	Output is correct
66	Correct	175 ms	30772 KB	Output is correct
67	Correct	214 ms	30316 KB	Output is correct
68	Correct	144 ms	38496 KB	Output is correct
69	Correct	230 ms	33400 KB	Output is correct
70	Correct	173 ms	30816 KB	Output is correct