Attraction Score (Problem B, The 2024 ICPC Asia Pacific Championship, 2024)
Time limit: 4 sec
Author: Jonathan Irvin Gunawan

# Problem Statement

There are $n$ cities, numbered from $1$ to $n$, in the fictional country of Manteiv. We can consider these cities to be on a flat plane with a 2D coordinate system, where city $i$ is at coordinates $(x_i, y_i)$. No two cities are located at the same position.

There are $m$ highways, numbered from $1$ to $m$, each of which is a line segment with two different cities as its endpoints and has a number of attraction points alongside it. Specifically, highway $j$ has $a_j$ attraction points and connects cities $u_j$ and $v_j$ as its endpoints. Having intersections on highways causes traffic jams, and building a highway on top of another highway costs a lot of money. Therefore, it is guaranteed that

- no two highways intersect at any point other than at a city,
- no highway passes through a city other than its two endpoints, and
- there is at most one highway connecting each pair of cities.

The Manteiv Ministry of Tourism would like to choose a subset of cities as tourist attractions. Intuitively, the ministry would like many pairs of chosen cities to be connected by a highway with many attraction points. Formally, the attraction score of a non-empty subset of cities $S$ is defined as follows:

- For every pair of integers $(a, b)$ where $a < b$, cities $a$ and $b$ are in $S$, and they are connected by a highway, add the number of attraction points on the highway to the score.

- Let $f(S)$ be the number of pairs of integers $(a, b)$ where $a < b$, cities $a$ and $b$ are in $S$, and they are not connected by a highway. The score incurs a penalty (negative) score of $10^6$ multiplied by the square of $f(S)$. In other words, subtract $10^6 \times f(S)^2$ from the score.

For example, let $n = 3$, cities 1 and 2 be connected by a highway with 10 attraction points, cities 2 and 3 be connected by a highway with 20 attraction points, and cities 1 and 3 not be connected by a highway.

- The attraction score of the subset of cities $\{1\}$ is 0.
- The attraction score of the subset of cities $\{1, 2\}$ is $10 - 10^6 \times 0^2 = 10$.
- The attraction score of the subset of cities $\{2, 3\}$ is $20 - 10^6 \times 0^2 = 20$.
- The attraction score of the subset of cities $\{1, 2, 3\}$ is $10 + 20 - 10^6 \times 1^2 = -999\,970$.

As an advisor to the ministry, you would like to find the maximum attraction score among all possible non-empty subsets of cities $S$.

# Input

The first line of input contains two integers $n$ and $m$ ($1 \le n \le 100\,000$; $0 \le m \le 300\,000$). Each of the next $n$ lines contains two integers. The $i$-th line contains $x_i$ and $y_i$ ($0 \le x_i, y_i \le 10^9$). Each of the next $m$ lines contains three integers. The $j$-th line contains $u_j$, $v_j$, and $a_j$ ($1 \le u_j < v_j \le n$; $0 \le a_j \le 10^6$). The highways are guaranteed to satisfy the conditions in the problem statement.

# Output

Output an integer representing the maximum attraction score among all possible non-empty subsets of cities S.

# Sample Input #1
```
3 2
0 0
0 1
1 0
1 2 10
2 3 20
```
# Sample Output #1
```
20
```
*Explanation for the sample input/output #1*

This sample is the example given in the problem statement above. The subset of cities {2, 3} gives the highest attraction score of 20.

# Sample Input #2
```
3 3
0 0
0 1
1 0
1 2 10
2 3 20
1 3 30
```
# Sample Output #2
```
60
```
*Explanation for the sample input/output #2*

The cities and highways are illustrated by Figure B.1. By choosing cities 1, 2, and 3 in $S$, the attraction score would be $10 + 20 + 30 - 10^6 \times 0^2 = 60$.

*Figure B.1: Illustration of sample input #2.*
![IMAGE](icpc-apac-2024-attraction-1.png)

Sample inputs:
3 2
0 0
0 1
1 0
1 2 10
2 3 20

3 3
0 0
0 1
1 0
1 2 10
2 3 20
1 3 30

Sample outputs:
20

60

# Solution Analysis
Analysis author: Jonathan Irvin Gunawan

Because the graph is planar, any subset of $v$ nodes (for $v > 2$) nodes can only contain at most $3v - 6$ edges between them.

**Observation B.1.**  
It is sufficient to check only clique subgraphs or cliques with one missing edge. We define this as our search space.

**Proof.**  
For $v > 6$, the score of any subgraph is not positive since $(3v - 6) - \binom{v}{2} - (3v - 6))^2 < 0$.

For $v = 6$, the maximum number of edges possible is 12, which means there are at least 3 missing edges (there are 15 edges in $K_6$). Let $x$ be a node with at least one missing edge, so its degree is at most 4. Removing $x$ decreases the number of edges by at most 4 but reduces the number of missing edges to 2 or less, hence saving a penalty of at least $(3^2 - 2^2) \times 10^6 = 5 \times 10^6$, which is more than the score of 4 edges, so it’s better to remove node $x$. Thus, we can focus on $v \leq 5$.

For $v = 5$, with two missing edges, the score is not better than if the node of minimum degree is removed. This reduced graph (without the node of minimum degree) is in our search space. With more than two missing edges, the score is negative.

For $v < 5$, the score is not positive if there is more than one missing edge.

We can enumerate all $O(n)$ clique subgraphs of a planar graph in $O(n \log n)$ time. To do that, we look at the node with the minimum degree (call this node $u$). Let the set of neighbours of node $u$ be $S_u$. Since the graph is planar, it is guaranteed that $|S_u| \leq 5$, so we can obtain all cliques containing node $u$ in $O(1)$. We then continue the algorithm by enumerating cliques without node $u$. We can do so by removing node $u$ from the graph and recursively doing the algorithm on the rest of the graph, which is still planar.

Thus, we can compute the maximum score among all clique subgraphs. We now focus on computing the maximum score among all subgraphs with 5 nodes and one missing edge. A similar argument can be applied to subgraphs with fewer nodes.

Consider node $u$ in the recursive algorithm above. The hard case is when the missing edge is *not* incident to $u$, because then one node in the subgraph is not in $S_u$. Let nodes $a$, $b$, and $c$ be the nodes in the subgraph that are in $S_u$. To find the missing node $d$ that maximizes the score, we can note that nodes $a$, $b$, $c$, and $d$ form a clique. We can also assume that there is no edge connecting nodes $u$ and $d$, so the optimal choice for $d$ is independent of $u$. Therefore, we can find this node $d$ in $O(1)$ by precomputing all $O(n)$ cliques.

This solution runs in $O(n \log n)$ time.

Special judge (C++ scorer):
/**
 * Default validator from https://github.com/Kattis/problemtools
 * Modified (as small as possible) to tcframe format by jonathanirvings.
 */

#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, double &val) {
  char trash[20];
  double v;
  if (sscanf(s, "%lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  bool case_sensitive = false;
  bool space_change_sensitive = false;
  bool use_floats = false;
  double float_abs_tol = -1;
  double float_rel_tol = -1;

  for (int a = 4; a < argc; ++a) {
    if        (!strcmp(argv[a], "case_sensitive")) {
      case_sensitive = true;
    } else if (!strcmp(argv[a], "space_change_sensitive")) {
      space_change_sensitive = true;
    } else if (!strcmp(argv[a], "float_absolute_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_abs_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_relative_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      float_abs_tol = float_rel_tol;
      ++a;
    } else {
      judge_error(USAGE, argv[0]);
    }
  }
  use_floats = float_abs_tol >= 0 || float_rel_tol >= 0;

  judgeans_pos = con_pos;
  judgeans_line = con_line = 1;
   
  std::string judge, team;
  char trash[20];
  while (true) {
    // Space!  Can't live with it, can't live without it...
    while (isspace(judgeans.peek())) {
      char c = (char)judgeans.get();
      if (space_change_sensitive) {
        int d = conans.get();
        if (c != d) {
          wrong_answer("Space change error: got %d expected %d", d, c);
        }
        if (d == '\n') ++con_line;
        ++con_pos;
      }
      if (c == '\n') ++judgeans_line;
      ++judgeans_pos;
    }
    while (isspace(conans.peek())) {
      char d = (char)conans.get();
      if (space_change_sensitive) {
        wrong_answer("Space change error: judge out of space, got %d from team", d);
      }
      if (d == '\n') ++con_line;
      ++con_pos;
    }

    if (!(judgeans >> judge))
      break;

    if (!(conans >> team)) {
      wrong_answer("User EOF while judge had more output\n(Next judge token: %s)", judge.c_str());
    }
     
    double jval, tval;
    if (use_floats && isfloat(judge.c_str(), jval)) {
      if (!isfloat(team.c_str(), tval)) {
        wrong_answer("Expected float, got: %s", team.c_str());
      }
      if(!(fabs(jval - tval) <= float_abs_tol) && 
         !(fabs(jval - tval) <= float_rel_tol*fabs(jval))) {
        wrong_answer("Too large difference.\n Judge: %s\n Team: %s\n Difference: %le\n (abs tol %le rel tol %le)", 
               judge.c_str(), team.c_str(), jval-tval, float_abs_tol, float_rel_tol);
      }
    } else if (case_sensitive) {
      if (strcmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    } else {
      if(strcasecmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    }
    judgeans_pos += judge.length();
    con_pos += team.length();
  }

  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}