Submission #132648

#	Time	Username	Problem	Language	Result	Execution time	Memory
132648		Just_Solve_The_Problem	Election Campaign (JOI15_election_campaign)	C++11	5 / 100	274 ms	32588 KiB

election_campaign

#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];
}

vector <int > st[N];
int id[N];

void dfs2(int v, int pr) {
  int big = 0;
  for (int to : gr[v]) {
    if (to == pr) continue;
    if (sz[to] > sz[big]) {
      big = to;
    }
    dfs2(to, v);
  }
  if (big) {
    id[v] = id[big];
  }
  int ok = -1;
  for (int idd : query[v]) {
    if (ok != -1) break;
    bool res = 1;
    for (int to : gr[v]) {
      res &= (st[id[to]].empty() || (check(idd, st[id[to]].back()) && check(st[id[to]].back(), idd)));
      if (!res) break;
    }
    if (res) {
      ok = idd;
    }
  }
  for (int to : gr[v]) {
    if (to == pr || big == to) continue;
    for (int tto : st[id[to]]) {
      st[id[v]].push_back(tto);
    }
  }
  if (ok != -1) {
    st[id[v]].push_back(ok);
  }
}

main() {
  scanf("%d", &n);
  iota(id, id + n + 1, 0);
  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", st[id[1]].size());
}

Compilation message (stderr)

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: At global scope:
election_campaign.cpp:200:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:233:34: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d\n", st[id[1]].size());
                  ~~~~~~~~~~~~~~~~^
election_campaign.cpp:201:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:205: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:210:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &m);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:213: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: 0 / 10
• Subtask 2: 5 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40