답안 #1073934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1073934	2024-08-25T04:27:38 Z	Persia	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	76 ms	51796 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;

void predfs(int u, int par) {
  in[u] = ++cnt;
  rn[cnt] = u;
  rmq[++ct][0] = in[u];
  h[in[u]] = ct;
  for(auto v : G[u]) if (v != par) {
    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;
}

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;
//    rep(i, 1, m) {
//      rep(j, 0, 2) cout << qq[i][j] << " ";
//      cout << "\n";
//    }
  }
}

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();
}

Compilation message

election_campaign.cpp: In function 'long long int sub1::sol()':
election_campaign.cpp:68:30: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   68 |       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:70:36: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   70 |         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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Runtime error	3 ms	5468 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2652 KB	Output is correct
2	Correct	2 ms	2820 KB	Output is correct
3	Correct	3 ms	2908 KB	Output is correct
4	Correct	61 ms	33184 KB	Output is correct
5	Correct	63 ms	33108 KB	Output is correct
6	Correct	58 ms	33224 KB	Output is correct
7	Correct	66 ms	33252 KB	Output is correct
8	Correct	58 ms	33108 KB	Output is correct
9	Correct	63 ms	33108 KB	Output is correct
10	Correct	56 ms	33104 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2652 KB	Output is correct
2	Correct	2 ms	2820 KB	Output is correct
3	Correct	3 ms	2908 KB	Output is correct
4	Correct	61 ms	33184 KB	Output is correct
5	Correct	63 ms	33108 KB	Output is correct
6	Correct	58 ms	33224 KB	Output is correct
7	Correct	66 ms	33252 KB	Output is correct
8	Correct	58 ms	33108 KB	Output is correct
9	Correct	63 ms	33108 KB	Output is correct
10	Correct	56 ms	33104 KB	Output is correct
11	Correct	7 ms	3676 KB	Output is correct
12	Correct	58 ms	33560 KB	Output is correct
13	Correct	64 ms	33764 KB	Output is correct
14	Correct	76 ms	33360 KB	Output is correct
15	Correct	60 ms	33484 KB	Output is correct
16	Correct	62 ms	33360 KB	Output is correct
17	Correct	60 ms	33360 KB	Output is correct
18	Correct	75 ms	33564 KB	Output is correct
19	Correct	58 ms	33360 KB	Output is correct
20	Correct	71 ms	33332 KB	Output is correct