Submission #1073943

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1073943	2024-08-25T04:53:04 Z	Persia	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	103 ms	49808 KB

election_campaign

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define rep2(i, l, r) for(int i = l; i >= r; i--)
#define fi first
#define se second
#define bit(i, x) (x >> i & 1)

using namespace std;
const int N = 1e5 + 3;
const int mod = 1e9 + 7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rnd(long long l, long long r) {
  return uniform_int_distribution<long long>(l, r)(rng);
}

int n, m;
vector<int> G[N];
pair<int, int> e[N];
array<int, 3> qq[N];
int in[N], out[N], rn[N], cnt;
int h[2 * N], rmq[2 * N][19], ct;
int f[N][18], dep[N];

void predfs(int u, int par) {
  in[u] = ++cnt;
  rn[cnt] = u;
  rmq[++ct][0] = in[u];
  h[in[u]] = ct;
  rep(i, 1, 17) f[u][i] = f[f[u][i - 1]][i - 1];
  for(auto v : G[u]) if (v != par) {
    f[v][0] = u;
    dep[v] = dep[u] + 1;
    predfs(v, u);
    rmq[++ct][0] = in[u];
  }
  out[u] = cnt;
}
int lca(int x, int y) {
  x = h[in[x]], y = h[in[y]];
  if (x > y) swap(x, y);
  int kk = 31 - __builtin_clz(y - x + 1);
  return rn[min(rmq[x][kk], rmq[y - (1 << kk) + 1][kk])];
}
bool path(int x, int y, int u) {
  bool flag = 0;
  flag |= (lca(y, u) == u && lca(x, u) == x);
  swap(x, y);
  flag |= (lca(y, u) == u && lca(x, u) == x);
  return flag;
}
bool check(int x, int y, int u, int v) {
  int p = lca(x, y);
  int g = lca(u, v);
  bool flag = 0;
  flag |= (path(p, x, u) || path(p, x, v) || path(p, x, g));
  flag |= (path(p, y, u) || path(p, y, v) || path(p, y, g));
  swap(x, u);
  swap(y, v);
  swap(p, g);
  flag |= (path(p, x, u) || path(p, x, v) || path(p, x, g));
  flag |= (path(p, y, u) || path(p, y, v) || path(p, y, g));
  return flag;
}
int jump(int x, int y) {
  if (x == y || !x || !y) return 0;
  if (dep[x] < dep[y]) swap(x, y);
  int delta = dep[x] - dep[y] - 1;
  rep(i, 0, 17) if (bit(i, delta)) x = f[x][i];
  return x;
}

namespace sub1{
  long long sol() {
    long long res = 0;
    rep(mask, 0, (1 << m) - 1) {
      long long s = 0;
      bool flag = 1;
      rep(i, 1, m) if (bit(i - 1, mask)) {
        s += qq[i][2];
        rep(j, i + 1, m) if (bit(j - 1, mask)) {
          if (check(qq[i][0], qq[i][1], qq[j][0], qq[j][1])) flag = 0;
        }
      }
      if (flag) res = max(res, s);
    }
    return res;
  }
}

namespace sub23{
  long long dp[N];
  long long sol() {
    rep(i, 1, n - 1) {
      assert(e[i].fi == i && e[i].se == i + 1);
    }
    sort(qq + 1, qq + m + 1, [&](array<int, 3> x, array<int, 3> y) {
      return x[1] < y[1];
    });
    long long res = 0;
    for(int i = 1, j = 1, k = 1; i <= m; ) {
      while(k <= qq[i][1]) {
        dp[k] = max(dp[k], dp[k - 1]);
        k++;
      }
      while(j <= m && qq[i][1] == qq[j][1]) {
        dp[qq[j][1]] = max(dp[qq[j][1]], dp[qq[j][0] - 1] + qq[j][2]);
        j++;
      }
      res = max(res, dp[qq[i][1]]);
      i = j;
    }
    return res;
  }
}

namespace sub6{
  long long dp[N][2];
  vector<array<int, 3>> g[N];
  void dfs(int u, int par) {
    for(auto v : G[u]) if (v != par) {
      dfs(v, u);
      dp[u][0] += dp[v][1];
    }
    dp[u][1] = dp[u][0];
    for(auto i : g[u]) {
      int x = (i[0] == u ? 0 : i[0]);
      int y = (i[1] == u ? 0 : i[1]);
      int c = i[2];
      dp[u][1] = max(dp[u][1], dp[x][0] + dp[y][0] + dp[u][0] - dp[jump(x, u)][1] - dp[jump(y, u)][1] + c);
    }
  }
  long long sol() {
    rep(i, 1, m) g[lca(qq[i][0], qq[i][1])].push_back(qq[i]);
    dfs(1, -1);
    return dp[1][1];
  }
}

int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

  // freopen("testing.txt", "r", stdin);
//  freopen("outputing.txt", "w", stdout);

  cin >> n;
  rep(i, 1, n - 1) {
    int u, v; cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
    e[i] = {u, v};
  }
  cin >> m;
  rep(i, 1, m) {
    int u, v, c; cin >> u >> v >> c;
    if (u > v) swap(u, v);
    qq[i] = {u, v, c};
  }
  predfs(1, -1);
  rep(j, 1, 18) rep(i, 1, ct - (1 << (j - 1))) rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
//  cout << sub1::sol();
//  cout << sub23::sol();
  cout << sub6::sol();
//  cout << jump(3, 5);
}

Compilation message

election_campaign.cpp: In function 'long long int sub1::sol()':
election_campaign.cpp:79:30: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   79 |       rep(i, 1, m) if (bit(i - 1, mask)) {
      |                            ~~^~~
election_campaign.cpp:6:25: note: in definition of macro 'bit'
    6 | #define bit(i, x) (x >> i & 1)
      |                         ^
election_campaign.cpp:81:36: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   81 |         rep(j, i + 1, m) if (bit(j - 1, mask)) {
      |                                  ~~^~~
election_campaign.cpp:6:25: note: in definition of macro 'bit'
    6 | #define bit(i, x) (x >> i & 1)
      |                         ^

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5208 KB	Output is correct
2	Correct	3 ms	5212 KB	Output is correct
3	Incorrect	3 ms	5464 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	2 ms	5212 KB	Output is correct
2	Correct	2 ms	5212 KB	Output is correct
3	Correct	3 ms	5468 KB	Output is correct
4	Correct	95 ms	49364 KB	Output is correct
5	Correct	96 ms	49488 KB	Output is correct
6	Correct	85 ms	49488 KB	Output is correct
7	Correct	87 ms	49352 KB	Output is correct
8	Correct	93 ms	49468 KB	Output is correct
9	Correct	84 ms	49492 KB	Output is correct
10	Correct	88 ms	49488 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	5212 KB	Output is correct
2	Correct	2 ms	5212 KB	Output is correct
3	Correct	3 ms	5468 KB	Output is correct
4	Correct	95 ms	49364 KB	Output is correct
5	Correct	96 ms	49488 KB	Output is correct
6	Correct	85 ms	49488 KB	Output is correct
7	Correct	87 ms	49352 KB	Output is correct
8	Correct	93 ms	49468 KB	Output is correct
9	Correct	84 ms	49492 KB	Output is correct
10	Correct	88 ms	49488 KB	Output is correct
11	Correct	8 ms	6492 KB	Output is correct
12	Correct	87 ms	49744 KB	Output is correct
13	Correct	84 ms	49744 KB	Output is correct
14	Correct	83 ms	49744 KB	Output is correct
15	Correct	85 ms	49748 KB	Output is correct
16	Correct	103 ms	49808 KB	Output is correct
17	Correct	88 ms	49748 KB	Output is correct
18	Correct	86 ms	49696 KB	Output is correct
19	Correct	80 ms	49748 KB	Output is correct
20	Correct	87 ms	49784 KB	Output is correct