Submission #1307586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307586		pandaa73	Telepathy (JOI25_telepathy)	C++20	0 / 100	2 ms	808 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 = 20;
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);

    vector<int> F(N), P(N), d(N + 1);
    auto dfs = [&](int v, auto &&dfs) -> void {
        for(auto u: adj[v]) {
            if(u == F[v]) continue;

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

            dfs(u, dfs);
        }
    };

    infof("... root = %d", root);

    F[root] = P[root] = root;
    d[N] = N + 1;

    dfs(root, dfs);

    P[root2] = root2;

    vector<int> head(N); iota(all(head), 0);
    vector<vector<int>> team(N);
    for(int i = 0; i < N; ++i) team[i] = {i};

    auto find_rec = [&](int v, auto &&find_rec) -> int {
        return team[v].size() ? v : P[v] = find_rec(P[v], find_rec);
    };

    auto find = [&](int v) -> int {
        return P[v] = find_rec(P[v], find_rec);
    };

    int mx_size = 1;

    bool done = 0;
    while(!done) {
        infof("-----");

        done = 1;

        int t1 = 0, t2 = 0;
        vector<int> l, r;
        auto dfs = [&](int v, auto &&dfs) -> int {
            int ret = N;
            for(auto u: adj[v]) {
                if(u == F[v]) continue;

                int s = dfs(u, dfs);

                if(d[s] < d[ret]) ret = s;
            }

            if(team[v].empty() || v == root2) return ret;

            done = 0;

            int pv = find(v);

            if(d[ret] > d[v]) ret = pv;

            int ch_t1 = 0, ch_t2 = 0;
            if(ret == v) {
                ch_t1 = d[v] - d[pv];
            }

            ch_t2 = d[v] - d[pv];

            if(pv == root || pv == root2) {
                if(ret == v) {
                    ch_t1 += 1;
                }

                ch_t2 += 1;
            }

            t1 = max(t1, ch_t1);
            t2 = max(t2, ch_t2);

            (ret == v ? l : r).emplace_back(v);

#ifdef DEBUG
            char c = ret == v ? 'l' : 'r';

            infof("... dfs: v = %d is \'%c\' [ret = %d]", v, c, ret);
#endif

            return ret;
        };

        for(auto u: adj[root]) {
            dfs(u, dfs);
        }

        auto concat = [&](vector<int> &a, const vector<int> &b) -> void {
            for(auto x: b) {
                a.emplace_back(x);
            }
        };

        mx_size += t1;
        for(auto v: l) {
            int pv = find(v);

            vector<int> p;
            for(int u = F[v]; u != pv; u = F[u]) {
                p.emplace_back(u);
            }

            p.emplace_back(pv);

            for(auto u: team[v]) {
                if(u != src) continue;

                infof("l: visited src with pv = %d", pv);
                infor("l: p:");
                for(auto x: p) {
                    infor(" %d", x);
                }
                infof("");

                concat(ans, p);
                ans.resize(mx_size, ans.back());
            }

            p.pop_back();
            reverse(all(p));
            p.emplace_back(v);

            for(auto u: team[v]) {
                if(u != src) continue;

                concat(ans, p);
                ans.resize(mx_size + t2, ans.back());
            }
        }

        for(auto v: r) {
            int pv = find(v);

            vector<int> p;
            for(int u = F[v]; u != pv; u = F[u]) {
                p.emplace_back(u);
            }

            p.emplace_back(pv);

            for(auto u: team[v]) {
                if(u != src) continue;

                infof("r: visited src with pv = %d", pv);
                infor("r: p:");
                for(auto x: p) {
                    infor(" %d", x);
                }
                infof("");

                ans.resize(mx_size, ans.back());
                concat(ans, p);
                ans.resize(mx_size + t2, ans.back());
            }

            for(auto x: team[v]) {
                head[x] = pv;
                team[pv].emplace_back(x);
            }

            team[v].clear();
            team[v].shrink_to_fit();
        }

        if(!is_bruno && root2 < N && src == root) {
            ans.resize(mx_size, root);
            ans.back() = root2;
        }

        mx_size += t2;

        if(!is_bruno && root2 < N && src == root) {
            ans.resize(mx_size, root);
            ans.back() = root2;
        }

#ifdef DEBUG
        infof("... t1 = %d | t2 = %d | mx_size = %d", t1, t2, mx_size);
        infof("... teams = {");
        for(int i = 0; i < N; ++i) {
            infor("...     %3d:", i);
            for(auto x: team[i]) {
                infor(" %d", x);
            }

            infof("");
        }

        infof("... }");
#endif
    }

    if(src == root) {
        ans.emplace_back(root);
    }
}

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);

    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());

//    if(c.second < N) {
//        int i;
//        for(i = 10 * N; i >= 0; i--) {
//            if(ans[i] != c.first) break;
//        }
//
//        for(i += 3 + (i&1); i < 10 * N + 1; i += 2) {
//            ans[i] = c.second;
//        }
//    }

    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);

    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());

    if(c.second < N) {
        int i;
        for(i = 10 * N; i >= 0; i--) {
            if(ans[i] != c.first) break;
        }

        for(i += 2; i < 10 * N + 1; i += 2) {
            ans[i] = c.second;
        }
    }

    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: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20