답안 #439149

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
439149	2021-06-29T10:03:31 Z	peijar	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	562 ms	44356 KB

election_campaign

#include <bits/stdc++.h>
#define int long long
using namespace std;

template <class T> class Fenwick {
public:
  int lim;
  vector<T> bit;

  Fenwick(int n) : lim(n + 1), bit(lim) {}

  void upd(int pos, T val) {
    for (pos++; pos < lim; pos += pos & -pos)
      bit[pos] += val;
  }

  T sum(int r) { // < r
    T ret = 0;
    for (; r; r -= r & -r)
      ret += bit[r];
    return ret;
  }

  T sum(int l, int r) { // [l, r)
    return sum(r) - sum(l);
  }
};

struct Voyage {
  int u, v, gain;
};

const int MAXN = 1e5;
const int MAXP = 17;

int par[MAXP][MAXN];
vector<int> adj[MAXN];
vector<Voyage> voyages[MAXN];
int depth[MAXN];
int timeIn[MAXN], timeOut[MAXN];
int curTime = 0;
int nbSommets, nbVoyages;
Fenwick<int> fen(0);

int dpAvec[MAXN], dpSans[MAXN];

int goUp(int u, int d) {
  for (int p = 0; p < MAXP; ++p)
    if ((1 << p) & d)
      u = par[p][u];
  return u;
}

int lca(int u, int v) {
  if (depth[u] < depth[v])
    swap(u, v);
  u = goUp(u, depth[u] - depth[v]);
  if (u == v)
    return u;
  for (int p = MAXP - 1; p >= 0; --p)
    if (par[p][u] != par[p][v])
      u = par[p][u], v = par[p][v];
  return par[0][u];
}

void dfs(int u, int p) {
  timeIn[u] = curTime++;
  for (auto v : adj[u])
    if (v != p) {
      depth[v] = depth[u] + 1;
      par[0][v] = u;
      dfs(v, u);
    }
  timeOut[u] = curTime++;
}

void subAdd(int iSommet, int x) {
  fen.upd(timeIn[iSommet], x);
  fen.upd(timeOut[iSommet] + 1, -x);
}

int pointQuery(int iSommet) { return fen.sum(timeIn[iSommet] + 1); }

void dfs2(int u) {
  for (auto v : adj[u]) {
    if (v == par[0][u])
      continue;
    dfs2(v);
    dpSans[u] += dpAvec[v];
  }
  dpAvec[u] = dpSans[u];
  for (auto voyage : voyages[u]) {
    int f1 = voyage.u, f2 = voyage.v;
    int solAvec = voyage.gain;
    if (f1 != u) {
      int p = goUp(f1, depth[f1] - depth[u] - 1);
      solAvec += pointQuery(f1) + dpSans[f1] - dpAvec[p];
    }
    if (f2 != u) {
      int p = goUp(f2, depth[f2] - depth[u] - 1);
      solAvec += pointQuery(f2) + dpSans[f2] - dpAvec[p];
    }
    solAvec += dpSans[u];
    dpAvec[u] = max(dpAvec[u], solAvec);
  }

  for (auto v : adj[u])
    if (v != par[0][u])
      subAdd(v, dpSans[u] - dpAvec[v]);
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> nbSommets;
  for (int i = 1; i < nbSommets; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(0, 0);
  for (int p = 0; p < MAXP - 1; ++p)
    for (int i = 0; i < nbSommets; ++i)
      par[p + 1][i] = par[p][par[p][i]];

  fen = Fenwick<int>(curTime);
  cin >> nbVoyages;
  for (int iVoyage = 0; iVoyage < nbVoyages; ++iVoyage) {
    int u, v, c;
    cin >> u >> v >> c;
    --u, --v;
    int l = lca(u, v);
    voyages[l].push_back({u, v, c});
  }
  dfs2(0);
  cout << dpAvec[0] << endl;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5068 KB	Output is correct
2	Correct	4 ms	5036 KB	Output is correct
3	Correct	4 ms	5068 KB	Output is correct
4	Correct	5 ms	5292 KB	Output is correct
5	Correct	131 ms	28888 KB	Output is correct
6	Correct	75 ms	39000 KB	Output is correct
7	Correct	134 ms	35580 KB	Output is correct
8	Correct	88 ms	28228 KB	Output is correct
9	Correct	98 ms	33452 KB	Output is correct
10	Correct	91 ms	28228 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5068 KB	Output is correct
2	Correct	4 ms	5068 KB	Output is correct
3	Correct	5 ms	5452 KB	Output is correct
4	Correct	175 ms	43852 KB	Output is correct
5	Correct	171 ms	43844 KB	Output is correct
6	Correct	157 ms	43788 KB	Output is correct
7	Correct	172 ms	43780 KB	Output is correct
8	Correct	169 ms	43804 KB	Output is correct
9	Correct	146 ms	43956 KB	Output is correct
10	Correct	170 ms	43904 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5068 KB	Output is correct
2	Correct	4 ms	5068 KB	Output is correct
3	Correct	5 ms	5452 KB	Output is correct
4	Correct	175 ms	43852 KB	Output is correct
5	Correct	171 ms	43844 KB	Output is correct
6	Correct	157 ms	43788 KB	Output is correct
7	Correct	172 ms	43780 KB	Output is correct
8	Correct	169 ms	43804 KB	Output is correct
9	Correct	146 ms	43956 KB	Output is correct
10	Correct	170 ms	43904 KB	Output is correct
11	Correct	20 ms	6628 KB	Output is correct
12	Correct	172 ms	44144 KB	Output is correct
13	Correct	166 ms	44052 KB	Output is correct
14	Correct	152 ms	44204 KB	Output is correct
15	Correct	196 ms	44088 KB	Output is correct
16	Correct	156 ms	44100 KB	Output is correct
17	Correct	195 ms	44216 KB	Output is correct
18	Correct	171 ms	44100 KB	Output is correct
19	Correct	202 ms	44136 KB	Output is correct
20	Correct	178 ms	44144 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	399 ms	33108 KB	Output is correct
2	Correct	163 ms	43812 KB	Output is correct
3	Correct	562 ms	39968 KB	Output is correct
4	Correct	212 ms	32732 KB	Output is correct
5	Correct	297 ms	39144 KB	Output is correct
6	Correct	219 ms	32568 KB	Output is correct
7	Correct	497 ms	38732 KB	Output is correct
8	Correct	272 ms	33136 KB	Output is correct
9	Correct	135 ms	43812 KB	Output is correct
10	Correct	470 ms	37408 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5068 KB	Output is correct
2	Correct	4 ms	5036 KB	Output is correct
3	Correct	4 ms	5068 KB	Output is correct
4	Correct	5 ms	5292 KB	Output is correct
5	Correct	131 ms	28888 KB	Output is correct
6	Correct	75 ms	39000 KB	Output is correct
7	Correct	134 ms	35580 KB	Output is correct
8	Correct	88 ms	28228 KB	Output is correct
9	Correct	98 ms	33452 KB	Output is correct
10	Correct	91 ms	28228 KB	Output is correct
11	Correct	4 ms	5324 KB	Output is correct
12	Correct	4 ms	5432 KB	Output is correct
13	Correct	5 ms	5436 KB	Output is correct
14	Correct	4 ms	5324 KB	Output is correct
15	Correct	5 ms	5308 KB	Output is correct
16	Correct	6 ms	5324 KB	Output is correct
17	Correct	6 ms	5324 KB	Output is correct
18	Correct	6 ms	5452 KB	Output is correct
19	Correct	7 ms	5428 KB	Output is correct
20	Correct	5 ms	5452 KB	Output is correct

Subtask #6
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5068 KB	Output is correct
2	Correct	4 ms	5036 KB	Output is correct
3	Correct	4 ms	5068 KB	Output is correct
4	Correct	5 ms	5292 KB	Output is correct
5	Correct	131 ms	28888 KB	Output is correct
6	Correct	75 ms	39000 KB	Output is correct
7	Correct	134 ms	35580 KB	Output is correct
8	Correct	88 ms	28228 KB	Output is correct
9	Correct	98 ms	33452 KB	Output is correct
10	Correct	91 ms	28228 KB	Output is correct
11	Correct	4 ms	5068 KB	Output is correct
12	Correct	4 ms	5068 KB	Output is correct
13	Correct	5 ms	5452 KB	Output is correct
14	Correct	175 ms	43852 KB	Output is correct
15	Correct	171 ms	43844 KB	Output is correct
16	Correct	157 ms	43788 KB	Output is correct
17	Correct	172 ms	43780 KB	Output is correct
18	Correct	169 ms	43804 KB	Output is correct
19	Correct	146 ms	43956 KB	Output is correct
20	Correct	170 ms	43904 KB	Output is correct
21	Correct	20 ms	6628 KB	Output is correct
22	Correct	172 ms	44144 KB	Output is correct
23	Correct	166 ms	44052 KB	Output is correct
24	Correct	152 ms	44204 KB	Output is correct
25	Correct	196 ms	44088 KB	Output is correct
26	Correct	156 ms	44100 KB	Output is correct
27	Correct	195 ms	44216 KB	Output is correct
28	Correct	171 ms	44100 KB	Output is correct
29	Correct	202 ms	44136 KB	Output is correct
30	Correct	178 ms	44144 KB	Output is correct
31	Correct	399 ms	33108 KB	Output is correct
32	Correct	163 ms	43812 KB	Output is correct
33	Correct	562 ms	39968 KB	Output is correct
34	Correct	212 ms	32732 KB	Output is correct
35	Correct	297 ms	39144 KB	Output is correct
36	Correct	219 ms	32568 KB	Output is correct
37	Correct	497 ms	38732 KB	Output is correct
38	Correct	272 ms	33136 KB	Output is correct
39	Correct	135 ms	43812 KB	Output is correct
40	Correct	470 ms	37408 KB	Output is correct
41	Correct	4 ms	5324 KB	Output is correct
42	Correct	4 ms	5432 KB	Output is correct
43	Correct	5 ms	5436 KB	Output is correct
44	Correct	4 ms	5324 KB	Output is correct
45	Correct	5 ms	5308 KB	Output is correct
46	Correct	6 ms	5324 KB	Output is correct
47	Correct	6 ms	5324 KB	Output is correct
48	Correct	6 ms	5452 KB	Output is correct
49	Correct	7 ms	5428 KB	Output is correct
50	Correct	5 ms	5452 KB	Output is correct
51	Correct	288 ms	33408 KB	Output is correct
52	Correct	200 ms	44356 KB	Output is correct
53	Correct	429 ms	37792 KB	Output is correct
54	Correct	181 ms	32824 KB	Output is correct
55	Correct	411 ms	33480 KB	Output is correct
56	Correct	215 ms	44104 KB	Output is correct
57	Correct	302 ms	38784 KB	Output is correct
58	Correct	250 ms	32996 KB	Output is correct
59	Correct	305 ms	33348 KB	Output is correct
60	Correct	192 ms	44108 KB	Output is correct
61	Correct	314 ms	38916 KB	Output is correct
62	Correct	247 ms	32400 KB	Output is correct
63	Correct	391 ms	33028 KB	Output is correct
64	Correct	205 ms	44104 KB	Output is correct
65	Correct	412 ms	38744 KB	Output is correct
66	Correct	192 ms	32628 KB	Output is correct
67	Correct	410 ms	33172 KB	Output is correct
68	Correct	217 ms	44112 KB	Output is correct
69	Correct	287 ms	37152 KB	Output is correct
70	Correct	268 ms	32732 KB	Output is correct

답안 #439149

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 5.0 / 5.0

Subtask #3 5.0 / 5.0

Subtask #4 30.0 / 30.0

Subtask #5 10.0 / 10.0

Subtask #6 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
5.0 / 5.0

Subtask #3
5.0 / 5.0

Subtask #4
30.0 / 30.0

Subtask #5
10.0 / 10.0

Subtask #6
40.0 / 40.0