oj.uz

Submission #132609

# Submission time Handle Problem Language Result Execution time Memory
132609 2019-07-19T08:31:57 Z Just_Solve_The_Problem Election Campaign (JOI15_election_campaign) C++11
20 / 100
 531 ms 28780 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];
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]];
  }
  for (int to : gr[v]) {
    if (to == pr) continue;
    dfs(to, v);
  }
  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;
  for (int to : gr[v]) {
    if (upper(to, a) || upper(to, b)) continue;
    res = max(res, dp[to]);
  }
  for (int to : gr[a]) {
    if (upper(to, a) || upper(to, b)) continue;
    res = max(res, dp[to]);
  }
  
  for (int to : gr[b]) {
    if (upper(to, a) || upper(to, b)) continue;
    res = max(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] = max(dp[v], dp[to]);
  }
  for (int id : query[v]) {
    dp[v] = max(dp[v], calc(v, id) + get<2>(vec[id]));
  }
}

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 && gr[n - 1][0] == n) {
    return solve2();
  }
  for (int i = 0; i < m; i++) {
    query[lca(get<0>(vec[i]), get<1>(vec[i]))].push_back(i);
  }
  dfs1(1, 1);
  cout << dp[1];
}

Compilation message

election_campaign.cpp: In function 'int solve1()':
election_campaign.cpp:81:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); i++) {
                     ~~^~~~~~~~~~
election_campaign.cpp:82:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < v.size(); j++) {
                       ~~^~~~~~~~~~
election_campaign.cpp: At global scope:
election_campaign.cpp:145:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:149: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:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &m);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:157: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 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 93 ms 5240 KB Output is correct
5 Correct 531 ms 16860 KB Output is correct
6 Correct 95 ms 21368 KB Output is correct
7 Correct 250 ms 19960 KB Output is correct
8 Correct 473 ms 17272 KB Output is correct
9 Correct 303 ms 19036 KB Output is correct
10 Correct 467 ms 17372 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 117 ms 28492 KB Output is correct
5 Correct 121 ms 28548 KB Output is correct
6 Correct 119 ms 28520 KB Output is correct
7 Correct 118 ms 28520 KB Output is correct
8 Correct 117 ms 28524 KB Output is correct
9 Correct 122 ms 28572 KB Output is correct
10 Correct 152 ms 28520 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 117 ms 28492 KB Output is correct
5 Correct 121 ms 28548 KB Output is correct
6 Correct 119 ms 28520 KB Output is correct
7 Correct 118 ms 28520 KB Output is correct
8 Correct 117 ms 28524 KB Output is correct
9 Correct 122 ms 28572 KB Output is correct
10 Correct 152 ms 28520 KB Output is correct
11 Correct 17 ms 6132 KB Output is correct
12 Correct 124 ms 28652 KB Output is correct
13 Correct 122 ms 28620 KB Output is correct
14 Correct 122 ms 28696 KB Output is correct
15 Correct 121 ms 28648 KB Output is correct
16 Correct 121 ms 28704 KB Output is correct
17 Correct 120 ms 28648 KB Output is correct
18 Correct 125 ms 28780 KB Output is correct
19 Correct 121 ms 28648 KB Output is correct
20 Correct 121 ms 28648 KB Output is correct

Subtask #4
0 / 30.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 93 ms 5240 KB Output is correct
5 Correct 531 ms 16860 KB Output is correct
6 Correct 95 ms 21368 KB Output is correct
7 Correct 250 ms 19960 KB Output is correct
8 Correct 473 ms 17272 KB Output is correct
9 Correct 303 ms 19036 KB Output is correct
10 Correct 467 ms 17372 KB Output is correct
11 Incorrect 8 ms 5308 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 93 ms 5240 KB Output is correct
5 Correct 531 ms 16860 KB Output is correct
6 Correct 95 ms 21368 KB Output is correct
7 Correct 250 ms 19960 KB Output is correct
8 Correct 473 ms 17272 KB Output is correct
9 Correct 303 ms 19036 KB Output is correct
10 Correct 467 ms 17372 KB Output is correct
11 Correct 6 ms 5112 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 7 ms 5240 KB Output is correct
14 Correct 117 ms 28492 KB Output is correct
15 Correct 121 ms 28548 KB Output is correct
16 Correct 119 ms 28520 KB Output is correct
17 Correct 118 ms 28520 KB Output is correct
18 Correct 117 ms 28524 KB Output is correct
19 Correct 122 ms 28572 KB Output is correct
20 Correct 152 ms 28520 KB Output is correct
21 Correct 17 ms 6132 KB Output is correct
22 Correct 124 ms 28652 KB Output is correct
23 Correct 122 ms 28620 KB Output is correct
24 Correct 122 ms 28696 KB Output is correct
25 Correct 121 ms 28648 KB Output is correct
26 Correct 121 ms 28704 KB Output is correct
27 Correct 120 ms 28648 KB Output is correct
28 Correct 125 ms 28780 KB Output is correct
29 Correct 121 ms 28648 KB Output is correct
30 Correct 121 ms 28648 KB Output is correct
31 Incorrect 214 ms 20332 KB Output isn't correct
32 Halted 0 ms 0 KB -