제출 #981758

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
981758		yoav_s	즐거운 행로 (APIO20_fun)	C++17	0 / 100	2043 ms	348 KiB

fun

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

typedef int ll;
typedef pair<ll,ll> p;
typedef pair<ll, p> tri;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<p> vp;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<vv> vvv;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef vector<vvvp> vvvvp;
#define double long double
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;

const ll mod = 1e9 + 7;
const ll INF = 1e18;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define loop(a) for (ll i = 0; i < a; i++)
#define setmin(a, b) a = min(a, b)
#define setmax(a, b) a = max(a, b)
#define all(v) v.begin(), v.end()

#include "fun.h"

ll getSubtreeSize(ll i, vv &graph, v &res)
{
    if (res[i] > -1) return 0;
    res[i] = 1;
    for (ll x : graph[i])
    {
        res[i] += getSubtreeSize(x, graph, res);
    }
    return res[i];
}

void getHeight(ll i, vv &graph, v &res, ll h)
{
    if (res[i] > -1) return;
    res[i] = h;
    for (ll x : graph[i]) getHeight(x, graph, res, h + 1);
}

void setGroup(ll i, vv &graph, v &res, ll g, ll c)
{
    if (res[i] != -1) return;
    res[i] = g;
    for (ll x : graph[i]) if (x != c) setGroup(x, graph, res, g, c);
}

std::vector<int> createFunTour(int N, int Q) {
    vv graph(N);
    for (ll i = 0; i < N; i++)
    {
        for (ll j = i + 1; j < N; j++)
        {
            if (hoursRequired(i, j) == 1)
            {
                graph[i].pb(j);
                graph[j].pb(i);
            }
        }
    }
    ll root = 0;
    v subtreeSize(N, -1);
    getSubtreeSize(root, graph, subtreeSize);
    ll centroid = 0;
    vb visited(N, false);
    while (true)
    {
        ll others = N - 1 - subtreeSize[centroid];
        bool poss = others <= N / 2;
        for (ll x : graph[centroid])
        {
            if (!visited[x] && subtreeSize[x] > N / 2) poss = false;
        }
        if (poss) break;
        ll maxi = -1, best = -1;
        for (ll x : graph[centroid])
        {
            if (!visited[x] && subtreeSize[x] > maxi)
            {
                maxi = subtreeSize[x];
                best = x;
            }
        }
        visited[best] = true;
        centroid = best;
    }
    root = centroid;
    v heights(N, -1);
    getHeight(root, graph, heights, 0);
    v group(N, -1);
    for (ll x : graph[centroid]) setGroup(x, graph, group, x, centroid);
    vp heightsSorted;
    for (ll i =0 ;i < N; i++) heightsSorted.eb(heights[i], i);
    sort(all(heightsSorted), greater<p>());
    visited = vb(N, false);
    vector<int> res;
    ll curG = -2;
    while (res.size() < N)
    {
        for (auto x : heightsSorted)
        {
            if (group[x.s] != curG && !visited[x.s])
            {
                curG = group[x.s];
                visited[x.s] = true;
                res.pb(x.s);
                break;
            }
        }
    }
    return res;
}

/*
static void wrongAnswer(std::string message) {
  printf("WA: %s\n", message.c_str());
  exit(0);
}

namespace tree_helper {

static int N;
static int logN;
static std::vector<std::vector<int>> parent;
static std::vector<int> depth;
static std::vector<int> subtree_size;

static void dfs(
    const std::vector<std::vector<int>>& adj_list,
    int current_node, int parent_node) {
  parent[0][current_node] = parent_node;
  subtree_size[current_node] = 1;
  for (int i = 0; i < static_cast<int>(adj_list[current_node].size()); ++i) {
    const int next_node = adj_list[current_node][i];
    if (next_node != parent_node) {
      depth[next_node] = depth[current_node] + 1;
      dfs(adj_list, next_node, current_node);
      subtree_size[current_node] += subtree_size[next_node];
    }
  }
}

static void initializeTree(const std::vector<std::vector<int>>& adj_list) {
  N = static_cast<int>(adj_list.size());

  depth = std::vector<int>(N, 0);
  subtree_size = std::vector<int>(N, 0);
  for (logN = 0; (1 << logN) < N; ++logN) {}
  parent = std::vector<std::vector<int>>(logN, std::vector<int>(N, 0));

  dfs(adj_list, 0, 0);
  for (int i = 1; i < logN; ++i) {
    for (int j = 0; j < N; ++j) {
      parent[i][j] = parent[i - 1][parent[i - 1][j]];
    }
  }
}

static int getLowestCommonAncestor(int X, int Y) {
  if (depth[X] < depth[Y]) {
    std::swap(X, Y);
  }
  for (int i = logN - 1; i >= 0; --i) {
    if (depth[parent[i][X]] >= depth[Y]) {
      X = parent[i][X];
    }
  }
  if (X == Y) {
    return X;
  }
  for (int i = logN - 1; i >= 0; --i) {
    if (parent[i][X] != parent[i][Y]) {
      X = parent[i][X];
      Y = parent[i][Y];
    }
  }
  return parent[0][X];
}

static int getDistance(int X, int Y) {
  return depth[X] + depth[Y] - 2 * depth[getLowestCommonAncestor(X, Y)];
}

static int attractionsBehind(int X, int Y) {
  if (X == Y) {
    return N;
  }
  for (int i = logN - 1; i >= 0; --i) {
    if (depth[parent[i][X]] > depth[Y]) {
      X = parent[i][X];
    }
  }
  if (Y == parent[0][X]) {
    return N - subtree_size[X];
  }
  return subtree_size[Y];
}

static void checkFunTour(const std::vector<int>& fun_tour) {
  if (static_cast<int>(fun_tour.size()) != N) {
    wrongAnswer("Invalid size");
  }

  std::vector<bool> visited_attractions(N, false);
  for (int i = 0; i < N; ++i) {
    if (fun_tour[i] < 0 || fun_tour[i] >= N) {
      wrongAnswer("Invalid index");
    }
    if (visited_attractions[fun_tour[i]]) {
      wrongAnswer("Repeated index");
    }
    visited_attractions[fun_tour[i]] = true;
  }

  int last_travel_time = getDistance(fun_tour[0], fun_tour[1]);
  for (int i = 2; i < N; ++i) {
    int travel_time = getDistance(fun_tour[i - 1], fun_tour[i]);
    if (travel_time > last_travel_time) {
      wrongAnswer("Tour is not fun");
    }
    last_travel_time = travel_time;
  }
}

}  // namespace tree_helper

static int N, Q;

int hoursRequired(int X, int Y) {
  if (--Q < 0) {
    wrongAnswer("Too many queries");
  }
  if (X < 0 || X >= N || Y < 0 || Y >= N) {
    wrongAnswer("Invalid index");
  }
  return tree_helper::getDistance(X, Y);
}

int attractionsBehind(int X, int Y) {
  if (--Q < 0) {
    wrongAnswer("Too many queries");
  }
  if (X < 0 || X >= N || Y < 0 || Y >= N) {
    wrongAnswer("Invalid index");
  }
  return tree_helper::attractionsBehind(X, Y);
}

int main() {
  assert(2 == scanf("%d %d", &N, &Q));

  std::vector<std::vector<int>> adj_list(N);
  for (int i = 0; i < N - 1; ++i) {
    int A, B;
    assert(2 == scanf("%d %d", &A, &B));
    adj_list[A].push_back(B);
    adj_list[B].push_back(A);
  }
  tree_helper::initializeTree(adj_list);

  std::vector<int> fun_tour = createFunTour(N, Q);
  tree_helper::checkFunTour(fun_tour);

  for (int i = 0; i < N; ++i) {
    printf("%d%c", fun_tour[i], " \n"[i == N - 1]);
  }
  return 0;
}
/**/

컴파일 시 표준 에러 (stderr) 메시지

fun.cpp:286:1: warning: "/*" within comment [-Wcomment]
  286 | /**/
      |  
fun.cpp:27:16: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 | const ll INF = 1e18;
      |                ^~~~
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:115:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  115 |     while (res.size() < N)
      |            ~~~~~~~~~~~^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34