Submission #66167424

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
constexpr int MAXN = 1'000'007;
constexpr int INF = 2'000'000'000;
constexpr ll INFF = 1'000'000'000'000'000'000LL;
constexpr ll MOD = 998'244'353;
#define mkp make_pair
#define F first
#define S second
#define pb emplace_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()

struct DSU {
  int n;
  vector<int> sz, p;

  void init(int _n) {
    n = _n;
    sz.resize(n + 1);
    p.resize(n + 1);
    for (int i = 0; i <= n; i++) {
      p[i] = i;
      sz[i] = 1;
    }
  }

  int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }

  void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y)
      return;
    if (sz[x] > sz[y])
      swap(x, y);
    sz[y] += sz[x];
    p[x] = y;
  }
} dsu;

int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<vector<int>> G(n);

  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].pb(v);
    G[v].pb(u);
  }
  vector<string> a(n);
  for (auto &i : a)
    cin >> i;

  vector<string> merged(n, string(n, '0'));
  vector<vector<pii>> next_path(n, vector<pii>(n));
  //   map<pii, pii> next_path;
  vector<vector<int>> len(n, vector<int>(n, 0));
  //   map<pii, int> len;
  vector<pii> ps;
  vector<int> v;
  function<void(int, int)> dfs = [&](int now, int p) {
    int x = (sz(v) ? v[0] : now), y = now;
    len[x][y] = sz(v);
    if (sz(v) > 2)
      next_path[x][y] = mkp(v[1], v.back());
    else
      next_path[x][y] = mkp(-1, -1);
    ps.pb(x, y);
    v.pb(now);

    for (int i : G[now]) {
      if (i != p) {
        dfs(i, now);
      }
    }
    v.pop_back();
  };
  for (int i = 0; i < n; i++)
    dfs(i, -1);

  dsu.init(n);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      if (a[i][j] != '1')
        continue;
      int x = i, y = j;
      while (x >= 0 && y >= 0 && x != y) {
        if (merged[x][y] == '1')
          break;
        dsu.merge(x, y);
        auto [xx, yy] = next_path[x][y];
        merged[x][y] = '1';
        x = xx, y = yy;
      }
    }

  vector<int> color(n);
  for (int i = 0; i < n; i++)
    color[i] = dsu.find(i);
  sort(all(ps), [&](pii x, pii y) { return len[x.F][x.S] < len[y.F][y.S]; });
  merged = vector<string>(n, string(n, '0'));

  int ans = 0;
  for (auto [x, y] : ps) {
    if (x == y) {
      merged[x][y] = '1';
      ans++;
    } else {
      auto [xx, yy] = next_path[x][y];
      if ((xx == -1 || merged[xx][yy] == '1') && color[x] == color[y]) {
        merged[x][y] = '1';
        ans++;
      }
    }
  }
  cout << ans << '\n';
}
/*
- How to come up with solutions? (https://hackmd.io/-3cIVAFSQMC3iJTh9EpszA)
  - Play with some small examples.
  - Make observations (or random guesses) by intuition.
    - Try to find counterexamples of the "observations."
  - Find the characteristics of an optimal solution.
  - Try to solve simple cases.
  - Brute force and print out the results.
  - Pick a method (greedy, dp, d&c, ...)
    - But DO NOT force algos on problems!
  - IF YOU'RE STUCK, TRY SOMETHING ELSE! Make new observations!

- Before writing the solution:
  - check TL/ML/correctness of samples/implementation details!

- Pre-submit:
  - Did you make a typo when copying a template?
  - Test more cases if unsure.
    - Write a naive solution and check small cases.
  - Submit the correct file.

- Debugging:
  - General Debugging:
    - Read the whole problem again.
    - Think over the algorithm again.
    - Go to the toilet.

  - Wrong Answer:
    - Any possible overflows?
      - > `__int128` ?
      - Try `-ftrapv` or `#pragma GCC optimize("trapv")`
    - Floating point errors?
      - > `long double` ?
      - turn off math optimizations
      - check for `==`, `>=`, `acos(1.000000001)`, etc.
    - Did you forget to sort or unique?
    - Generate large and worst "corner" cases.
    - Check your `m` / `n`, `i` / `j`,  `x` / `y` and `<` / `>`.
    - Are everything initialized or reset properly?
    - Are you sure about the STL thing you are using?
      - Read cppreference.
    - Print everything and run it on pen and paper.

  - Time Limit Exceeded:
    - Calculate your time complexity again.
    - Does the program actually end?
      - Check for `while(q.size())` etc.
    - Test the largest cases locally.
    - Did you do unnecessary stuff?
      - e.g. pass vectors by value
      - e.g. `memset` for every test case
    - Is your constant factor reasonable?

  - Runtime Error:
    - Check memory usage.
      - Forget to clear or destroy stuff?
      - > `vector::shrink_to_fit()`
    - Stack overflow?
    - Bad pointer / array access?
      - Try `-fsanitize=address`
    - Division by zero? NaN's?
*/

Submission Info

Judge Result