제출 #1253120

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253120		madamadam3	이주 (IOI25_migrations)	C++20	20 / 100	30 ms	1736 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>

using namespace std;

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

void dfs(int u, int p, vi &dist, vvi &adj) {
  for (auto &v : adj[u]) {
    if (v == p) continue;
    dist[v] = dist[u] + 1;
    dfs(v, u, dist, adj);
  }
}

int furthest_from(int u, int n, vvi &adj) {
  vector<int> dist(n);
  dfs(u, u, dist, adj);

  int f = 0; for (int i = 0; i < n; i++) if (dist[i] > dist[f]) f = i;
  return f;
}

pi furthest_pair(int n, vvi &adj) {
  vector<int> dist(n);
  dfs(0, 0, dist, adj);
  int f1 = 0; for (int i = 0; i < n; i++) if (dist[i] > dist[f1]) f1 = i;
  dist = vi(n, 0);
  dfs(f1, f1, dist, adj);
  int f2 = 0; for (int i = 0; i < n; i++) if (dist[i] > dist[f2]) f2 = i;

  return {min(f1, f2), max(f1, f2)};
}

vvi adj;
pi fr;

int send_message(int n, int i, int Pi) {
  if (i <= 1) adj.assign(n+1, vi());

  adj[Pi].push_back(i);
  adj[i].push_back(Pi);

  // if (i >= n - 18) {
  //   int furthest = furthest_from(0, n, adj);
  //   int bit = i - (n - 18);

  //   if (furthest == i) {
  //     return 2;
  //   } else {
  //     return (furthest & (1 << bit)) ? 1 : 0;
  //   }
  // }
  if (i == n - 2) {
    fr = furthest_pair(n, adj);
    return fr.first;
  } else if (i == n - 1) {
    auto f = furthest_pair(n, adj);
    if (f.first == fr.first && f.second == fr.second) {
      return f.second;
    } else {
      return 10000 + f.first;
    }
  }
  return 0;
}

pi longest_path(vi S) {
  int n = S.size();
  if (S[n-1] >= 10000) {
    return {n-1, S[n-1] - 10000};
  } else {
    return {S[n-1], S[n-2]};
  }

  // int pf = 0;
  // for (int i = max(0, n - 18); i < n; i++) if (S[i] == 2) pf = i;
  // if (pf != 0) return {0, pf};

  // for (int i = n - 18; i < n; i++) {
  //   pf += S[i] << (i - (n - 18));
  // }

  // return {0, pf};
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 30
• Subtask 2: 10.0003 / 70