oj.uz

Submission #132534

# Submission time Handle Problem Language Result Execution time Memory
132534 2019-07-19T06:34:20 Z Just_Solve_The_Problem Election Campaign (JOI15_election_campaign) C++11
20 / 100
 525 ms 22636 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];

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;
  }
  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--;
    }
  }
  printf("%d\n", 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:100:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:104: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:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &m);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:112: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 4 ms 2680 KB Output is correct
2 Correct 4 ms 2684 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 92 ms 2808 KB Output is correct
5 Correct 525 ms 13688 KB Output is correct
6 Correct 94 ms 18120 KB Output is correct
7 Correct 233 ms 16504 KB Output is correct
8 Correct 506 ms 13816 KB Output is correct
9 Correct 312 ms 15484 KB Output is correct
10 Correct 468 ms 13944 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 5 ms 2936 KB Output is correct
4 Correct 116 ms 22024 KB Output is correct
5 Correct 105 ms 22152 KB Output is correct
6 Correct 103 ms 22120 KB Output is correct
7 Correct 105 ms 22120 KB Output is correct
8 Correct 105 ms 21992 KB Output is correct
9 Correct 105 ms 22096 KB Output is correct
10 Correct 105 ms 22116 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 5 ms 2936 KB Output is correct
4 Correct 116 ms 22024 KB Output is correct
5 Correct 105 ms 22152 KB Output is correct
6 Correct 103 ms 22120 KB Output is correct
7 Correct 105 ms 22120 KB Output is correct
8 Correct 105 ms 21992 KB Output is correct
9 Correct 105 ms 22096 KB Output is correct
10 Correct 105 ms 22116 KB Output is correct
11 Correct 15 ms 3768 KB Output is correct
12 Correct 108 ms 22336 KB Output is correct
13 Correct 109 ms 22336 KB Output is correct
14 Correct 109 ms 22636 KB Output is correct
15 Correct 108 ms 22448 KB Output is correct
16 Correct 108 ms 22380 KB Output is correct
17 Correct 108 ms 22460 KB Output is correct
18 Correct 107 ms 22380 KB Output is correct
19 Correct 108 ms 22344 KB Output is correct
20 Correct 108 ms 22376 KB Output is correct

Subtask #4
0 / 30.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2684 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 92 ms 2808 KB Output is correct
5 Correct 525 ms 13688 KB Output is correct
6 Correct 94 ms 18120 KB Output is correct
7 Correct 233 ms 16504 KB Output is correct
8 Correct 506 ms 13816 KB Output is correct
9 Correct 312 ms 15484 KB Output is correct
10 Correct 468 ms 13944 KB Output is correct
11 Incorrect 5 ms 2936 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2684 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 92 ms 2808 KB Output is correct
5 Correct 525 ms 13688 KB Output is correct
6 Correct 94 ms 18120 KB Output is correct
7 Correct 233 ms 16504 KB Output is correct
8 Correct 506 ms 13816 KB Output is correct
9 Correct 312 ms 15484 KB Output is correct
10 Correct 468 ms 13944 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 4 ms 2808 KB Output is correct
13 Correct 5 ms 2936 KB Output is correct
14 Correct 116 ms 22024 KB Output is correct
15 Correct 105 ms 22152 KB Output is correct
16 Correct 103 ms 22120 KB Output is correct
17 Correct 105 ms 22120 KB Output is correct
18 Correct 105 ms 21992 KB Output is correct
19 Correct 105 ms 22096 KB Output is correct
20 Correct 105 ms 22116 KB Output is correct
21 Correct 15 ms 3768 KB Output is correct
22 Correct 108 ms 22336 KB Output is correct
23 Correct 109 ms 22336 KB Output is correct
24 Correct 109 ms 22636 KB Output is correct
25 Correct 108 ms 22448 KB Output is correct
26 Correct 108 ms 22380 KB Output is correct
27 Correct 108 ms 22460 KB Output is correct
28 Correct 107 ms 22380 KB Output is correct
29 Correct 108 ms 22344 KB Output is correct
30 Correct 108 ms 22376 KB Output is correct
31 Incorrect 169 ms 15116 KB Output isn't correct
32 Halted 0 ms 0 KB -