제출 #1030413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1030413		vjudge1	즐거운 행로 (APIO20_fun)	C++17	21 / 100	92 ms	16424 KiB

fun

//#define LOCAL
#ifndef LOCAL
#include "fun.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
vector<int> createFunTour(int N, int Q);
#include <cassert>
#include <cstdio>

#include <algorithm>
#include <string>
#include <vector>

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;
}
#endif
using namespace std;
vector<int>ans;
void makedouble(vector<pair<int,int>>a,vector<pair<int,int>>b){
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    while(a.size()||b.size()){
        ans.push_back(b.back().second);
        b.pop_back();
        swap(a,b);
    }
}
vector<pair<int,int>>concat(vector<pair<int,int>> a,vector<pair<int,int>> b){
    for(auto i:b)
        a.push_back(i);
    return a;
}
void stuff(vector<pair<int,int>>why[3],int a,int b,int c,int k){
    if(k-a) makedouble(concat(why[b],why[c]),why[a]);
    else makedouble(why[a],concat(why[b],why[c]));
}
vector<int> createFunTour(int N, int Q) {
    if(N==2) return{0,1};
    pair<int,int>centroid{N,0};
    for(int i=1;i<N;i++) {
        int k=attractionsBehind(0,i);
        if(k>=(N+1)/2)
            centroid=min(centroid,{k,i});
    }
    int k=centroid.second;
    vector<int>subtreez;
    vector<pair<int,int>> why[3];
    for(int i=0;i<N;i++){
        if(i==k) continue;
        int C=hoursRequired(k,i);
        if(!subtreez.size()){
            subtreez.push_back(i);
            why[0].push_back({C,i});
        } else if(subtreez.size()==1){
            if(why[0][0].first+C-hoursRequired(why[0][0].second,i))
                why[0].push_back({C,i});
            else subtreez.push_back(i),why[1].push_back({C,i});
        } else {
            if(why[0][0].first+C-hoursRequired(why[0][0].second,i))
                why[0].push_back({C,i});
            else if(why[1][0].first+C-hoursRequired(why[1][0].second,i))
                why[1].push_back({C,i});
            else why[2].push_back({C,i});
        }
    }
    sort(why[0].begin(),why[0].end());
    sort(why[1].begin(),why[1].end());
    sort(why[2].begin(),why[2].end());
    sort(why,why+3,[](vector<pair<int,int>>&a,vector<pair<int,int>>&b){
        return a.size()>b.size();
    });
    if(why[2].empty()){
        makedouble(why[1],why[0]);
    } else if(why[0].size()>=why[1].size()+why[2].size()){
        makedouble(concat(why[1],why[2]), why[0]);
    } else {
        sort(why,why+3,[](vector<pair<int,int>>&a,vector<pair<int,int>>&b){
            return a.back()>b.back();
        });
        int prv=0;
        ans.push_back(why[0].back().second);
        why[0].pop_back();
        while(1){
            pair<int,int>s{0,0};
            for(int i=0;i<3;i++)
                if(i-prv)s=max(s,{why[i].back().first,i});
            prv=s.second;
            ans.push_back(why[prv].back().second);
            why[prv].pop_back();
            int A=why[0].size(),B=why[1].size(),C=why[2].size();
            if(A+B==C){
                stuff(why,2,0,1,prv);
            } else if (A+C==B){
                stuff(why,1,2,0,prv);
            } else if (B+C==A){
                stuff(why,0,1,2,prv);
            } else {
                continue;
            }
            break;
        }
    }
    ans.push_back(k);
    return ans;
}

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