Submission #1309593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309593		pandaa73	Telepathy (JOI25_telepathy)	C++20	24 / 100	73 ms	904 KiB

telepathy

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

#define ff endl
#define lf "\n"
#define _ << ' ' <<
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)

#define infor(str, ...) do { fprintf(stderr, str, ##__VA_ARGS__); } while(0)
#define infof(str, ...) do { fprintf(stderr, str"\n", ##__VA_ARGS__); } while(0)

#ifndef DEBUG

#undef infor
#undef infof

#define infor(str, ...)
#define infof(str, ...)

#endif

using ll = long long;

using pll = pair<ll, ll>;
using pii = pair<int, int>;

constexpr int LOG = 8; // > LOG(200, 2)
constexpr int MOD = 1e9+7;
constexpr int MAXN = 1e5+7;

pii find_close_centroid(int N, int src, const vector<vector<int>> &adj) {
    vector<int> sz(N), d(N + 1);
    auto dfs = [&](int v, int f, auto &&dfs) -> void {
        sz[v] = 1;

        for(auto u: adj[v]) {
            if(u == f) continue;

            d[u] = 1 + d[v];

            dfs(u, v, dfs);

            sz[v] += sz[u];
        }
    };

    dfs(src, -1, dfs);
    d[N] = N + 1;

    pii cand = {N, N};
    auto find_centroid = [&](int v, int f, auto &&find_centroid) -> void {
        for(auto u: adj[v]) {
            if(u == f || 2 * sz[u] < N) continue; // note that N/2 rounds down
            if(sz[u] == N / 2) {
                cand = {u, v};
                return;
            }

            return find_centroid(u, v, find_centroid);
        }

        cand.first = v;
    };

    find_centroid(src, -1, find_centroid);

    if(d[cand.first] > d[cand.second]) swap(cand.first, cand.second);

    return cand;
}

void solve(int N, int root, int root2, const vector<vector<int>> &adj,
        int src, vector<int> &ans, bool is_bruno) {
    ans.emplace_back(src);

    set<int> alive;
    vector<int> F(N), d(N);

    auto dfs = [&](int v, auto &&dfs) -> void {
        alive.emplace(v);

        for(auto u: adj[v]) {
            if(u == F[v]) continue;

            F[u] = v;
            d[u] = 1 + d[v];
            dfs(u, dfs);
        }
    };

    F[root] = root2;
    dfs(root, dfs);
    F[root] = root;

    alive.erase(root);

    int mx_size = 1;
    for(int lg = 0; lg < LOG; ++lg) {
        infof("===== lg = %d =====", lg);
        infof("... src = %d", src);

        const int pow = 1 << lg;

        vector<int> path;

        vector<int> rm;
        for(auto v: alive) {
            if(d[v] % (2 * pow) == 0) continue;

            rm.emplace_back(v);
        }

        for(auto v: rm) {
            alive.erase(v);
        }

        if(src == root) {
            if(root2 < N && is_bruno) {
                ans.emplace_back(root2);
            }
        } else {
            int u = src;
            for(int i = 0; i < pow; ++i) {
                u = F[u];
                path.emplace_back(u);
            }

            if(alive.find(src) != alive.end()) {
                for(auto v: path) {
                    ans.emplace_back(v);
                }
            }
        }

        mx_size += pow;
        ans.resize(mx_size, ans.back());

        if(root2 < N) {
            if(src == root && is_bruno) {
                ans.emplace_back(root);
            }

            mx_size++;
            ans.resize(mx_size, ans.back());
        }

        if(src != root) {
            if(d[src] % (2 * pow) == 0) {
                infor("... path:");
                for(auto x: path) {
                    infor(" %d", x);
                }

                infof("");

                path.pop_back();
                reverse(all(path));
                path.emplace_back(src);
            } else src = path.back();

            for(auto v: path) {
                ans.emplace_back(v);
            }
        }

        mx_size += pow;
        ans.resize(mx_size, ans.back());
    }
}

vector<int> Aitana(int N, vector<int> A, vector<int> B, int src, int subtask) {
    infof("----- Aitana -----");
    infof("... N = %d | src = %d", N, src);

    vector<vector<int>> adj(N);

    for(int i = 0; i < N - 1; ++i) {
        adj[A[i]].emplace_back(B[i]);
        adj[B[i]].emplace_back(A[i]);
    }

    pii c = find_close_centroid(N, src, adj);

    if(c.second < c.first) {
        c.first = c.second;
    } else c.second = c.first;

    infof("... c = {%d, %d}", c.first, c.second);

    vector<int> ans;
    ans.reserve(10 * N + 1);

    solve(N, c.first, c.second, adj, src, ans, 0);
    ans.resize(10 * N + 1, ans.back());

    infor("ans:");
    for(auto x: ans) {
        infor(" %d", x);
    }
    infof("");

    return ans;
}

vector<int> Bruno(int N, vector<int> A, vector<int> B, int src, int subtask) {
    infof("----- Bruno  -----");
    infof("... N = %d | src = %d", N, src);

    vector<vector<int>> adj(N);

    for(int i = 0; i < N - 1; ++i) {
        adj[A[i]].emplace_back(B[i]);
        adj[B[i]].emplace_back(A[i]);
    }

    pii c = find_close_centroid(N, src, adj);

    if(c.second < c.first) {
        c.first = c.second;
    } else c.second = c.first;

    infof("... c = {%d, %d}", c.first, c.second);

    vector<int> ans;
    ans.reserve(10 * N + 1);

    solve(N, c.first, c.second, adj, src, ans, 1);
    ans.resize(10 * N + 1, ans.back());

    infor("ans:");
    for(auto x: ans) {
        infor(" %d", x);
    }
    infof("");

    return ans;
}

#ifdef LOCAL
namespace {
const int INVALID_X_LENGTH = 1;
const int INVALID_X_RANGE = 2;
const int INVALID_X_START = 3;
const int INVALID_X_PATH = 4;
const int INVALID_Y_LENGTH = 5;
const int INVALID_Y_RANGE = 6;
const int INVALID_Y_START = 7;
const int INVALID_Y_PATH = 8;
const int INVALID_MEET = 9;

std::mt19937_64 mt;
int case_id;
void WrongAnswer(int code) {
  printf("Case #%d: Wrong Answer [%d]\n", case_id, code);
}
int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input.\n");
    exit(1);
  }
  return x;
}
bool check_permutation(int N, const std::vector<int>& p) {
  std::vector<bool> f(N, false);
  for (int x : p) {
    if (!(0 <= x && x < N)) return false;
    if (f[x]) return false;
    f[x] = true;
  }
  return true;
}
bool check_tree(int N, const std::vector<int>& u, const std::vector<int>& v) {
  std::vector<std::vector<int>> G(N);
  for (int i = 0; i < N - 1; i++) {
    if (!(0 <= u[i] && u[i] < N)) {
      return false;
    }
    if (!(0 <= v[i] && v[i] < N)) {
      return false;
    }
    G[u[i]].push_back(v[i]);
    G[v[i]].push_back(u[i]);
  }
  std::vector<bool> vis(N, false);
  std::vector<int> st = {0};
  vis[0] = true;
  while (!st.empty()) {
    int u = st.back();
    st.pop_back();
    for (int i : G[u]) {
      if (!vis[i]) {
        vis[i] = true;
        st.push_back(i);
      }
    }
  }
  return (vis == std::vector<bool>(N, true));
}
std::string check_validness(int N, const std::vector<int>& u,
                            const std::vector<int>& v,
                            const std::vector<int>& p,
                            const std::vector<int>& q, int s, int t,
                            int subtask) {
  if (!(1 <= subtask && subtask <= 3)) return "1 <= subtask <= 3";
  if (!check_permutation(N, p)) return "p is not a permutation";
  if (!check_permutation(N, q)) return "q is not a permutation";
  if (!check_tree(N, u, v)) return "(u, v) does not form a tree";
  if (!(0 <= s && s < N && 0 <= t && t < N && s != t)) return "Invalid s or t";
  if (subtask == 1) {
    for (int i = 0; i < N; i++) {
      if (!(p[i] == i && q[i] == i)) {
        return "(p, q) does not meet the condition for subtask 1";
      }
    }
  }
  if (subtask == 2) {
    for (int i = 0; i < N - 1; i++) {
      if (!(u[i] == i && v[i] == i + 1)) {
        return "(u, v) does not meet the condition for subtask 2";
      }
    }
  }
  return "";
}
void shuffle_edge(int M, std::vector<int>& u, std::vector<int>& v) {
  for (int i = 0; i < M; i++) {
    if (mt() % 2 == 1) {
      std::swap(u[i], v[i]);
    }
    int x = mt() % (i + 1);
    std::swap(u[i], u[x]);
    std::swap(v[i], v[x]);
  }
}
int tree_distance(int N, const std::vector<int>& u, const std::vector<int>& v,
                  int s, int t) {
  std::vector<std::vector<int>> G(N);
  for (int i = 0; i < N - 1; i++) {
    G[u[i]].push_back(v[i]);
    G[v[i]].push_back(u[i]);
  }
  std::vector<int> dist(N, -1);
  dist[s] = 0;
  std::queue<int> que;
  que.push(s);
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    for (int i : G[u]) {
      if (dist[i] == -1) {
        dist[i] = dist[u] + 1;
        que.push(i);
      }
    }
  }
  return dist[t];
}
void run_scenario(int N, const std::vector<int>& u, const std::vector<int>& v,
                  const std::vector<int>& p, const std::vector<int>& q, int s,
                  int t, int subtask) {
  std::vector<int> invp(N), invq(N);
  for (int i = 0; i < N; i++) {
    invp[p[i]] = i;
    invq[q[i]] = i;
  }

  infor("invp [A]:");
  for(auto i: invp) {
      infor(" %d", i);
  }
  infof("");

  infor("invq [B]:");
  for(auto i: invq) {
      infor(" %d", i);
  }
  infof("");

  std::vector<int> A(N - 1), B(N - 1), C(N - 1), D(N - 1);
  std::vector<std::pair<int, int>> edges(N - 1);
  for (int i = 0; i < N - 1; i++) {
    A[i] = p[u[i]];
    B[i] = p[v[i]];
    C[i] = q[u[i]];
    D[i] = q[v[i]];
    edges[i] = std::minmax({u[i], v[i]});
  }
  shuffle_edge(N - 1, A, B);
  shuffle_edge(N - 1, C, D);
  int S = p[s];
  int T = q[t];
  std::sort(edges.begin(), edges.end());
  auto adjacent = [&](int a, int b) -> bool {
    return std::binary_search(edges.begin(), edges.end(), std::minmax({a, b}));
  };

#ifdef DEBUG
  std::fprintf(stderr, "===== START OF TEST =====\n");
#endif
  std::vector<int> x = Aitana(N, A, B, S, subtask);
  if (int(x.size()) != 10 * N + 1) return WrongAnswer(INVALID_X_LENGTH);
  for (int i = 0; i <= 10 * N; i++) {
    if (!(0 <= x[i] && x[i] < N)) return WrongAnswer(INVALID_X_RANGE);
  }
  if (!(x[0] == S)) return WrongAnswer(INVALID_X_START);
  for (int i = 0; i < 10 * N; i++) {
    if (!(x[i] == x[i + 1] || adjacent(invp[x[i]], invp[x[i + 1]]))) {
      return WrongAnswer(INVALID_X_PATH);
    }
  }
  std::vector<int> y = Bruno(N, C, D, T, subtask);
  if (int(y.size()) != 10 * N + 1) {
    return WrongAnswer(INVALID_Y_LENGTH);
  }
  for (int i = 0; i <= 10 * N; i++) {
    if (!(0 <= y[i] && y[i] < N)) {
      return WrongAnswer(INVALID_Y_RANGE);
    }
  }
  if (!(y[0] == T)) return WrongAnswer(INVALID_Y_START);
  for (int i = 0; i < 10 * N; i++) {
    if (!(y[i] == y[i + 1] || adjacent(invq[y[i]], invq[y[i + 1]]))) {
      return WrongAnswer(INVALID_Y_PATH);
    }
  }
  int meet = -1;
  for (int i = 0; i <= 10 * N; i++) {
    if (invp[x[i]] == invq[y[i]]) {
      meet = i;
      break;
    }
  }
  if (meet == -1) {
      infof("----- Grader -----");
      infor("Aitana:");
      for(auto i: x) {
          infor(" %d", invp[i]);
      }
      infof("");

      infor("Bruno:");
      for(auto i: y) {
          infor(" %d", invq[i]);
      }
      infof("");

      return WrongAnswer(INVALID_MEET);
  }

  int dist = tree_distance(N, u, v, s, t);
  printf("Case #%d: Accepted %d %d\n", case_id, meet, dist);
}
}  // namespace

int main(int argc, char* argv[]) {
  if (!(argc == 1 || argc == 2)) {
    fprintf(stderr, "usage: %s [<seed>]", argv[0]);
    exit(1);
  }
  if (argc == 2) {
    try {
      const long long seed = std::stoll(argv[1]);
      mt = std::mt19937_64(seed);
    } catch (const std::exception& e) {
      fprintf(stderr, "Invalid seed: %s\n", argv[1]);
      exit(1);
    }
  }
  int subtask = read_int();
  int Q = read_int();
  std::vector<int> N(Q), s(Q), t(Q);
  std::vector<std::vector<int>> p(Q), q(Q), u(Q), v(Q);
  for (int i = 0; i < Q; i++) {
    N[i] = read_int();
    u[i].resize(N[i] - 1);
    v[i].resize(N[i] - 1);
    for (int j = 0; j < N[i] - 1; j++) {
      u[i][j] = read_int();
      v[i][j] = read_int();
    }
    p[i].resize(N[i]);
    q[i].resize(N[i]);
    for (int& x : p[i]) x = read_int();
    for (int& x : q[i]) x = read_int();
    s[i] = read_int();
    t[i] = read_int();
  }
  for (int i = 0; i < Q; i++) {
    std::string err =
        check_validness(N[i], u[i], v[i], p[i], q[i], s[i], t[i], subtask);
    if (!err.empty()) {
      fprintf(stderr, "Input does not satisfy the constraints: %s\n",
              err.c_str());
      exit(1);
    }
  }

  for (int i = 0; i < Q; i++) {
    case_id = i;
    run_scenario(N[i], u[i], v[i], p[i], q[i], s[i], t[i], subtask);
  }
  return 0;
}
#endif

• Subtask 1: 24.4 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20