oj.uz

Submission #132678

# Submission time Handle Problem Language Result Execution time Memory
132678 2019-07-19T10:23:40 Z Just_Solve_The_Problem Election Campaign (JOI15_election_campaign) C++11
30 / 100
 536 ms 25224 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e5 + 7;

vector <int> gr[N];
int n, m;
vector <tuple<int, int, int>> vec;
int tin[N], tout[N], lc[17][N], sz[N];
int tiktak;

void dfs(int v, int pr) {
  tin[v] = ++tiktak;
  lc[0][v] = pr;
  for (int i = 1; i < 17; i++) {
    lc[i][v] = lc[i - 1][lc[i - 1][v]];
  }
  sz[v] = 1;
  for (int to : gr[v]) {
    if (to == pr) continue;
    dfs(to, v);
    sz[v] += sz[to];
  }
  tout[v] = ++tiktak;
}

bool upper(int a, int b) {
  return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
  if (upper(a, b)) return a;
  if (upper(b, a)) return b;
  for (int i = 16; i >= 0; i--) {
    if (!upper(lc[i][a], b)) a = lc[i][a];
  }
  return lc[0][a];
}

bool check(int i, int j) {
  int a, b, c, d, val = 0;
  tie(a, b) = make_tuple(get<0>(vec[i]), get<1>(vec[i]));
  tie(c, d) = make_tuple(get<0>(vec[j]), get<1>(vec[j]));
  int lc = lca(c, d);
  if (upper(a, b)) {
    val = (tin[a] <= tin[c] && tin[c] <= tin[b]);
    val ^= (tin[a] <= tout[c] && tout[c] <= tin[b]);
    if (val) return 0;
    val = (tin[a] <= tin[d] && tin[d] <= tin[b]);
    val ^= (tin[a] <= tout[d] && tout[d] <= tin[b]);
    if (val) return 0;
    val = (tin[a] <= tin[lc] && tin[lc] <= tin[b]);
    val ^= (tin[a] <= tout[lc] && tout[lc] <= tin[b]);
    if (val) return 0;
  } else {
    val = (tout[a] <= tin[c] && tin[c] <= tin[b]);
    val ^= (tout[a] <= tout[c] && tout[c] <= tin[b]);
    if (val) return 0;
    val = (tout[a] <= tin[d] && tin[d] <= tin[b]);
    val ^= (tout[a] <= tout[d] && tout[d] <= tin[b]);
    if (val) return 0;
    val = (tout[a] <= tin[lc] && tin[lc] <= tin[b]);
    val ^= (tout[a] <= tout[lc] && tout[lc] <= tin[b]);
    if (val) return 0;
    int lc1 = lca(a, b);
    if (lc1 == a || lc1 == b || lc1 == lc) return 0;
  }
  return 1;
}

int ans;

int solve1() {
  for (int mask = 1; mask < (1 << m); mask++) {
    vector <int> v;
    for (int j = 0; j < m; j++) {
      if ((mask >> j) & 1) {
        v.push_back(j);
      }
    }
    bool ok = 1;
    for (int i = 0; i < v.size(); i++) {
      for (int j = 0; j < v.size(); j++) {
        if (i == j) continue;
        ok &= check(v[i], v[j]);
      }
    }
    if (ok) {
      int res = 0;
      for (int &to : v) {
        res += get<2>(vec[to]);
      }
      ans = max(ans, res);
    }
  }
  return ans;
}

int dp[N];

int solve2() {
  sort(vec.begin(), vec.end());
  int ptr = vec.size() - 1;
  for (int i = n; i >= 1; i--) {
    dp[i] = dp[i + 1];
    while (ptr >= 0 && get<0>(vec[ptr]) == i) {
      dp[i] = max(dp[i], dp[get<1>(vec[ptr]) + 1] + get<2>(vec[ptr]));
      ptr--;
    }
  }
  return dp[1];
}

vector <int> query[N];

int calc(int v, int id) {
  int a, b;
  tie(a, b) = make_tuple(get<0>(vec[id]), get<1>(vec[id]));
  int res = 0;
  while (a != v) {
    for (int to : gr[a]) {
      if (upper(to, get<0>(vec[id])) || upper(to, get<1>(vec[id]))) continue;
      res += dp[to];
    }
    a = lc[0][a];
  }
  while (b != v) {
    for (int to : gr[b]) {
      if (upper(to, get<0>(vec[id])) || upper(to, get<1>(vec[id]))) continue;
      res += dp[to];
    }
    b = lc[0][b];
  }
  for (int to : gr[v]) {
    if (upper(to, get<0>(vec[id])) || upper(to, get<1>(vec[id]))) continue;
    res += dp[to];
  }
  return res;
}

void dfs1(int v, int pr) {
  for (int to : gr[v]) {
    if (to == pr) continue;
    dfs1(to, v);
    dp[v] += dp[to];
  }
  for (int id : query[v]) {
    dp[v] = max(dp[v], calc(v, id) + get<2>(vec[id]));
  }
}

int solve5() {
  for (int i = 0; i < m; i++) {
    query[lca(get<0>(vec[i]), get<1>(vec[i]))].push_back(i);
    //cout << i << ": " << lca(get<0>(vec[i]), get<1>(vec[i])) << endl;
  }
  dfs1(1, 1);
  return dp[1];
}

struct fen {
  int tree[N + N];
  fen() {
    memset(tree, 0, sizeof tree);
  }
  void upd(int pos, int val) {
    while (pos < N) {
      tree[pos] += val;
      pos = pos | pos + 1;
    }
  }
  int get(int r) {
    int res = 0;
    while (r >= 0) {
      res += tree[r];
      r = (r & r + 1) - 1;
    }
    return res;
  }
  int get(int l, int r) {
    return get(r) - get(l - 1);
  }
};
fen tr;
int siz[N];

void dfs2(int v, int pr) {
  for (int to : gr[v]) {
    if (to == pr) continue;
    dfs2(to, v);
    siz[v] += siz[to];
  }
  int ok = -1;
  for (int idd : query[v]) {
    if (tr.get(tin[v], tin[get<0>(vec[idd])]) == 0 && tr.get(tin[v], tin[get<1>(vec[idd])]) == 0) {
      ok = idd;
      break;
    }
  }
  if (ok != -1) {
    siz[v]++;
    tr.upd(tin[v], 1);
    tr.upd(tout[v], -1);
  }
}

main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    gr[u].push_back(v);
    gr[v].push_back(u);
  }
  dfs(1, 1);
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    if (tin[u] > tin[v]) swap(u, v);
    vec.push_back({u, v, w});
  }
  if (m <= 15) {
    printf("%d\n", solve1());
    return 0;
  }
  if (gr[1][0] == 2 && (n == 2 || gr[n - 1][1] == n)) {
    printf("%d\n", solve2());
    return 0;
  }
  if (n <= 1000 && m <= 1000) {
    printf("%d\n", solve5());
    return 0;
  }
  for (int i = 0; i < m; i++) {
    query[lca(get<0>(vec[i]), get<1>(vec[i]))].push_back(i);
  }
  dfs2(1, 1);
  printf("%d\n", siz[1]);
}

Compilation message

election_campaign.cpp: In function 'int solve1()':
election_campaign.cpp:83:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); i++) {
                     ~~^~~~~~~~~~
election_campaign.cpp:84:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < v.size(); j++) {
                       ~~^~~~~~~~~~
election_campaign.cpp: In member function 'void fen::upd(int, int)':
election_campaign.cpp:170:23: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
       pos = pos | pos + 1;
                   ~~~~^~~
election_campaign.cpp: In member function 'int fen::get(int)':
election_campaign.cpp:177:18: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
       r = (r & r + 1) - 1;
                ~~^~~
election_campaign.cpp: At global scope:
election_campaign.cpp:208:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:209:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:212:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &u, &v);
     ~~~~~^~~~~~~~~~~~~~~~~
election_campaign.cpp:217:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &m);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:220:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &u, &v, &w);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 7 ms 5880 KB Output is correct
3 Correct 7 ms 5880 KB Output is correct
4 Correct 94 ms 6008 KB Output is correct
5 Correct 536 ms 17144 KB Output is correct
6 Correct 100 ms 23160 KB Output is correct
7 Correct 258 ms 21112 KB Output is correct
8 Correct 480 ms 17400 KB Output is correct
9 Correct 318 ms 19832 KB Output is correct
10 Correct 488 ms 17528 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 7 ms 5880 KB Output is correct
3 Correct 8 ms 6136 KB Output is correct
4 Correct 110 ms 24852 KB Output is correct
5 Correct 110 ms 24816 KB Output is correct
6 Correct 110 ms 24944 KB Output is correct
7 Correct 111 ms 24812 KB Output is correct
8 Correct 109 ms 24820 KB Output is correct
9 Correct 110 ms 24960 KB Output is correct
10 Correct 110 ms 24812 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 7 ms 5880 KB Output is correct
3 Correct 8 ms 6136 KB Output is correct
4 Correct 110 ms 24852 KB Output is correct
5 Correct 110 ms 24816 KB Output is correct
6 Correct 110 ms 24944 KB Output is correct
7 Correct 111 ms 24812 KB Output is correct
8 Correct 109 ms 24820 KB Output is correct
9 Correct 110 ms 24960 KB Output is correct
10 Correct 110 ms 24812 KB Output is correct
11 Correct 18 ms 6712 KB Output is correct
12 Correct 114 ms 24996 KB Output is correct
13 Correct 115 ms 24944 KB Output is correct
14 Correct 113 ms 24944 KB Output is correct
15 Correct 114 ms 25224 KB Output is correct
16 Correct 114 ms 25012 KB Output is correct
17 Correct 114 ms 24952 KB Output is correct
18 Correct 113 ms 25032 KB Output is correct
19 Correct 114 ms 25032 KB Output is correct
20 Correct 115 ms 25124 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 19308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 7 ms 5880 KB Output is correct
3 Correct 7 ms 5880 KB Output is correct
4 Correct 94 ms 6008 KB Output is correct
5 Correct 536 ms 17144 KB Output is correct
6 Correct 100 ms 23160 KB Output is correct
7 Correct 258 ms 21112 KB Output is correct
8 Correct 480 ms 17400 KB Output is correct
9 Correct 318 ms 19832 KB Output is correct
10 Correct 488 ms 17528 KB Output is correct
11 Correct 9 ms 6008 KB Output is correct
12 Correct 10 ms 6136 KB Output is correct
13 Correct 9 ms 6136 KB Output is correct
14 Correct 9 ms 6012 KB Output is correct
15 Correct 8 ms 6136 KB Output is correct
16 Correct 9 ms 6008 KB Output is correct
17 Correct 9 ms 6056 KB Output is correct
18 Correct 10 ms 6264 KB Output is correct
19 Correct 8 ms 6012 KB Output is correct
20 Correct 8 ms 6136 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 7 ms 5880 KB Output is correct
3 Correct 7 ms 5880 KB Output is correct
4 Correct 94 ms 6008 KB Output is correct
5 Correct 536 ms 17144 KB Output is correct
6 Correct 100 ms 23160 KB Output is correct
7 Correct 258 ms 21112 KB Output is correct
8 Correct 480 ms 17400 KB Output is correct
9 Correct 318 ms 19832 KB Output is correct
10 Correct 488 ms 17528 KB Output is correct
11 Correct 7 ms 5880 KB Output is correct
12 Correct 7 ms 5880 KB Output is correct
13 Correct 8 ms 6136 KB Output is correct
14 Correct 110 ms 24852 KB Output is correct
15 Correct 110 ms 24816 KB Output is correct
16 Correct 110 ms 24944 KB Output is correct
17 Correct 111 ms 24812 KB Output is correct
18 Correct 109 ms 24820 KB Output is correct
19 Correct 110 ms 24960 KB Output is correct
20 Correct 110 ms 24812 KB Output is correct
21 Correct 18 ms 6712 KB Output is correct
22 Correct 114 ms 24996 KB Output is correct
23 Correct 115 ms 24944 KB Output is correct
24 Correct 113 ms 24944 KB Output is correct
25 Correct 114 ms 25224 KB Output is correct
26 Correct 114 ms 25012 KB Output is correct
27 Correct 114 ms 24952 KB Output is correct
28 Correct 113 ms 25032 KB Output is correct
29 Correct 114 ms 25032 KB Output is correct
30 Correct 115 ms 25124 KB Output is correct
31 Incorrect 219 ms 19308 KB Output isn't correct
32 Halted 0 ms 0 KB -