oj.uz

답안 #132612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132612 2019-07-19T08:35:34 Z Just_Solve_The_Problem Election Campaign (JOI15_election_campaign) C++11
20 / 100
 538 ms 27260 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 += dp[to];
  }
  if (a != v)
    for (int to : gr[a]) {
      if (upper(to, a) || upper(to, b)) continue;
      res += dp[to];
    }
  for (int to : gr[b]) {
    if (upper(to, a) || upper(to, b)) 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] = 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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5116 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 5388 KB Output is correct
5 Correct 538 ms 16796 KB Output is correct
6 Correct 96 ms 21240 KB Output is correct
7 Correct 239 ms 19576 KB Output is correct
8 Correct 478 ms 17016 KB Output is correct
9 Correct 310 ms 18656 KB Output is correct
10 Correct 467 ms 16888 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5368 KB Output is correct
4 Correct 118 ms 26980 KB Output is correct
5 Correct 117 ms 26988 KB Output is correct
6 Correct 116 ms 27088 KB Output is correct
7 Correct 117 ms 26984 KB Output is correct
8 Correct 118 ms 27112 KB Output is correct
9 Correct 116 ms 26988 KB Output is correct
10 Correct 117 ms 26984 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5368 KB Output is correct
4 Correct 118 ms 26980 KB Output is correct
5 Correct 117 ms 26988 KB Output is correct
6 Correct 116 ms 27088 KB Output is correct
7 Correct 117 ms 26984 KB Output is correct
8 Correct 118 ms 27112 KB Output is correct
9 Correct 116 ms 26988 KB Output is correct
10 Correct 117 ms 26984 KB Output is correct
11 Correct 17 ms 6132 KB Output is correct
12 Correct 137 ms 27164 KB Output is correct
13 Correct 129 ms 27112 KB Output is correct
14 Correct 119 ms 27244 KB Output is correct
15 Correct 146 ms 27116 KB Output is correct
16 Correct 120 ms 27240 KB Output is correct
17 Correct 120 ms 27168 KB Output is correct
18 Correct 136 ms 27204 KB Output is correct
19 Correct 133 ms 27260 KB Output is correct
20 Correct 120 ms 27116 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 228 ms 18800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5116 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 5388 KB Output is correct
5 Correct 538 ms 16796 KB Output is correct
6 Correct 96 ms 21240 KB Output is correct
7 Correct 239 ms 19576 KB Output is correct
8 Correct 478 ms 17016 KB Output is correct
9 Correct 310 ms 18656 KB Output is correct
10 Correct 467 ms 16888 KB Output is correct
11 Incorrect 7 ms 5240 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5116 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 5388 KB Output is correct
5 Correct 538 ms 16796 KB Output is correct
6 Correct 96 ms 21240 KB Output is correct
7 Correct 239 ms 19576 KB Output is correct
8 Correct 478 ms 17016 KB Output is correct
9 Correct 310 ms 18656 KB Output is correct
10 Correct 467 ms 16888 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 5368 KB Output is correct
14 Correct 118 ms 26980 KB Output is correct
15 Correct 117 ms 26988 KB Output is correct
16 Correct 116 ms 27088 KB Output is correct
17 Correct 117 ms 26984 KB Output is correct
18 Correct 118 ms 27112 KB Output is correct
19 Correct 116 ms 26988 KB Output is correct
20 Correct 117 ms 26984 KB Output is correct
21 Correct 17 ms 6132 KB Output is correct
22 Correct 137 ms 27164 KB Output is correct
23 Correct 129 ms 27112 KB Output is correct
24 Correct 119 ms 27244 KB Output is correct
25 Correct 146 ms 27116 KB Output is correct
26 Correct 120 ms 27240 KB Output is correct
27 Correct 120 ms 27168 KB Output is correct
28 Correct 136 ms 27204 KB Output is correct
29 Correct 133 ms 27260 KB Output is correct
30 Correct 120 ms 27116 KB Output is correct
31 Incorrect 228 ms 18800 KB Output isn't correct
32 Halted 0 ms 0 KB -