Submission #1146254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146254		peterandvoi	The Ties That Guide Us (CEOI23_incursion)	C++20	30 / 100	121 ms	6572 KiB

incursion

#include "incursion.h"

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "C:\debug.h"
#else
#define debug(...) 42
#endif

// If we can root the tree and HLD it then the problem is solved
// Using the property that a tree only have at most 2 centroid
// what a delight finding out this :D

vector<int> mark(vector<pair<int, int>> F, int safe) {
  --safe;
  int N = 0;
  vector<vector<int>> g;
  for (auto [u, v] : F) {
    N = max({N, u--, v--});
    g.resize(N);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<int> sz(N), Max(N);
  auto dfs = [&](auto self, int u, int p) -> void {
    sz[u] = 1;
    for (int v : g[u]) {
      if (v ^ p) {
        self(self, v, u);
        sz[u] += sz[v];
        Max[u] = max(Max[u], sz[v]);
      }
    }   
  };
  dfs(dfs, 0, 0);
  vector<int> cens;
  for (int i = 0; i < N; ++i) {
    if (max(Max[i], N - sz[i]) > N / 2) {
      continue;
    }
    cens.push_back(i);
  }
  int root = cens[0];
  vector<int> col(N, 0);
  auto DFS = [&](auto self, int u, int p) -> bool {
    if (u == safe) {
      col[u] = 1;
      return 1;
    }
    for (int v : g[u]) {
      if (v ^ p && self(self, v, u)) {
        col[u] = find(cens.begin(), cens.end(), v) == cens.end();
        return 1;
      }
    }
    return 0;
  };
  assert(DFS(DFS, root, root));
  return col;
}  

void locate(vector<pair<int, int>> F, int curr, int color) {
  --curr;
  int N = 0;
  vector<vector<int>> g;
  for (auto [u, v] : F) {
    N = max({N, u--, v--});
    g.resize(N);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<int> sz(N), Max(N);
  auto dfs = [&](auto self, int u, int p) -> void {
    sz[u] = 1;
    for (int v : g[u]) {
      if (v ^ p) {
        self(self, v, u);
        sz[u] += sz[v];
        Max[u] = max(Max[u], sz[v]);
      }
    }   
  };
  dfs(dfs, 0, 0);
  vector<int> cens;
  for (int i = 0; i < N; ++i) {
    if (max(Max[i], N - sz[i]) > N / 2) {
      continue;
    }
    cens.push_back(i);
  }
  assert(cens.size() <= 2);
  vector<int> pr(N);
  fill(sz.begin(), sz.end(), 0);
  auto DFS = [&](auto self, int u) -> void {
    sz[u] = 1;
    for (int v : g[u]) {
      g[v].erase(find(g[v].begin(), g[v].end(), u));
      pr[v] = u;
      self(self, v);
      sz[u] += sz[v];
    }
  };
  int root = cens[0];
  assert(cens.size() == 1 || find(g[root].begin(), g[root].end(), cens[1]) != g[root].end());
  DFS(DFS, root);
  // go up to root
  int lst = -1;
  while (color == 0 && curr ^ root) {
    color = visit(pr[curr] + 1);
    lst = curr;
    curr = pr[curr];
  }
  if (color == 0) {
    assert(cens.size() == 2);
    color = visit(cens[1] + 1);
    assert(color == 1);
    lst = curr;
    curr = cens[1];
  }
  if (lst != -1) {
    g[curr].erase(find(g[curr].begin(), g[curr].end(), lst));
  }
  // go down to the answer (do sth similar to HLD)
  auto solve = [&](int u) {
    if (g[u].empty()) {
      return false;
    }
    int x = *max_element(g[u].begin(), g[u].end(), [&](int a, int b) {
      return sz[a] < sz[b];
    });
    if (visit(x + 1)) {
      curr = x;
      return true;
    }
    visit(u + 1);
    for (int v : g[u]) {
      if (v ^ x) {
        if (visit(v + 1)) {
          curr = v;
          return true;
        }
        visit(u + 1);
      }
    }
    return false;
  };
  while (solve(curr));
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40