Submission #1307458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307458		pandaa73	Telepathy (JOI25_telepathy)	C++20	0 / 100	1305 ms	2228224 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, const vector<vector<int>> &adj,
        vector<vector<int>> &ans) {
    for(int i = 0; i < N; ++i) {
        ans[i].emplace_back(i);
    }

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

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

            dfs(u, dfs);
        }
    };

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

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

    dfs(root, dfs);

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

    int mx_size = 0;
    for(const auto &v: ans) {
        mx_size = max(mx_size, (int)v.size());
    }

    bool done = 0;
    while(!done) {
        done = 1;

        for(auto v: team[root])
            ans[v].emplace_back(root);

        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 == P[u]) continue;

                int s = dfs(u, dfs);

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

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

            done = 0;

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

            if(ret == v) {
                t1 = max(t1, d[v] - d[P[v]]);
            }

            t2 = max(t2, d[v] - d[P[v]]);

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

            return ret;
        };

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

        auto concat = [&](vector<int> &a, const vector<int> &b) -> void {
            a.reserve(a.size() + b.size());

            for(auto x: b) {
                a.emplace_back(x);
            }
        };

        mx_size += t1;
        for(auto v: l) {
            vector<int> p;
            for(int u = v; u != P[v]; u = F[u]) {
                p.emplace_back(u);
            }

            p.emplace_back(P[v]);

            for(auto u: team[v]) {
                concat(ans[u], p);
                ans[u].resize(mx_size, ans[u].back());
            }

            reverse(all(p));

            for(auto u: team[v]) {
                concat(ans[u], p);
                ans[u].resize(mx_size + t2, ans[u].back());
            }
        }

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

            p.emplace_back(P[v]);

            for(auto u: team[v]) {
                ans[u].resize(mx_size, ans[u].back());
                concat(ans[u], p);
                ans[u].resize(mx_size + t2, ans[u].back());
            }

            if(team[v].size() > team[P[v]].size()) {
                swap(team[v], team[P[v]]);
            }

            concat(team[P[v]], team[v]);

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

        mx_size += t2;
    }

    for(auto &v: ans) {
        v.resize(10 * N + 1, v.back());
    }
}

vector<int> Aitana(int N, vector<int> A, vector<int> B, int src, int subtask) {
    infof("----- Aitana -----");

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

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

    solve(N, c.first, adj, ans);

    if(c.second < N)
        ans[src].emplace_back(c.first);

    return ans[src];
}

vector<int> Bruno(int N, vector<int> A, vector<int> B, int src, int subtask) {
    infof("----- Bruno -----");

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

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

    solve(N, c.second < N ? c.second : c.first, adj, ans);
    if(c.second < N)
        ans[src].emplace_back(c.first);

    return ans[src];
}

#ifdef DEBUG
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;
  }
  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}));
  };

  std::fprintf(stderr, "===== START OF TEST =====\n");
  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) 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