제출 #981538

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

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#include <vector>
const int N =  1e5;
vector<vector<int>> adj(N);
vector<int> traversal;
vector<int> depth;
vector<int> ind(N);

void LCM(int s, int v, int d)
{
  ind[s] = (int)traversal.size();
  traversal.push_back(s);
  depth.push_back(d);

  for (auto u: adj[s])
  {
    if (u == v) continue;
    LCM(u, s, d+1);
    traversal.push_back(s);
    depth.push_back(d);
  }
}

struct SegmentTree {
  vector<pair<int, int>> t;

  SegmentTree(int power) : t(power) {}
  
  pair<int, int> combine(pair<int, int> a, pair<int, int> b) {
      if (a.first < b.first) return a;
      else return b;
  }
  
  void build(vector<int>& a, int v, int tl, int tr) {
      if (tl == tr) {
          if (tl < (int)a.size()) t[tl] = {depth[tl], a[tl]};
          else t[tl] = {N+1, N+1};
      } else {
          int tm = (tl + tr) / 2;
          build(a, v*2, tl, tm);
          build(a, v*2+1, tm+1, tr);
          t[v] = combine(t[v*2], t[v*2+1]);
      }
  }
  
  pair<int, int> query(int v, int tl, int tr, int l, int r) {
      if (l > r) return make_pair(N+1, N+1);
      if (l == tl && r == tr) return t[v];
      int tm = (tl + tr) / 2;
      return combine(query(v*2, tl, tm, l, min(r, tm)), 
                     query(v*2+1, tm+1, tr, max(l, tm+1), r));
  }
};

vector<int> parent(N);
void dfs(int s, int v)
{
  parent[s] = v;
  for (auto u: adj[s])
  {
    if (u == v) continue;
    dfs(u, s);
  }
}

std::vector<int> createFunTour(int n, int q) {
	queue<int> que;
  int start = 0;
  que.push(start);
  vector<int> leave;
  while (!que.empty()) {
      int s = que.front(); que.pop();
      for (int i=0; i<n; i++)
      {
        int h = hoursRequired(s, i);
        if (h == 1) {adj[s].push_back(i); adj[i].push_back(s);}
      }
      if ((int)adj[s].size() == 1) {leave.push_back(s);}
      for (auto u : adj[s]) 
      {
        que.push(u);
      }
  }
  vector<int> answer;
  if ((int)leave.size() == 2) {for (int i=0; i<n; i++) {answer.push_back(i);}}
  return answer;

  LCM(0, -1, 1);

  int volume = (int)traversal.size();
  int powtwo = __lg(volume) + !!(volume & (volume-1));
  SegmentTree segtree(powtwo); segtree.build(traversal, 1, 0, powtwo-1);
  int central = segtree.query(1, 0, powtwo-1, ind[leave[0]], ind[leave[1]]).second;

  vector<int> processing;
  tuple<int, int, int> prepath = {0, -1, -1};
  tuple<int, int, int> currpath = {0, -1, -1};
  vector<bool> visited(n);
  for (auto u: leave) {processing.push_back(u);}
  
  for (auto u: processing)
  {
    for (auto v: processing)
    {
      int h = hoursRequired(u, v);
      if (h > get<0>(prepath)) prepath = {h, u, v};
    }
  }
  visited[get<1>(prepath)] = true;
  visited[get<2>(prepath)] = true;
  processing.erase(find(processing.begin(), processing.end(), get<1>(prepath)));
  processing.erase(find(processing.begin(), processing.end(), get<1>(prepath)));
  

  while (!processing.empty()) {
    int u = get<1>(prepath);
    int v = get<2>(prepath);
    for (auto s: processing) {
      if (visited[s]) continue;
      int h = hoursRequired(u, s);
      if (h > get<0>(currpath)) currpath = {h, u, s};
    }
    for (auto s: processing) {
      if (visited[s]) continue;
      int h = hoursRequired(v, s);
      if (h > get<0>(currpath)) currpath = {h, v, s};
    }
    int s = get<2>(currpath);
    if (get<1>(currpath) == u) {answer.push_back(v); answer.push_back(u); answer.push_back(s);}
    else {answer.push_back(u); answer.push_back(v); answer.push_back(s);}
    visited[u] = visited[v] = visited[s] = true;
    if (parent[s] != central) {processing.push_back(parent[s]);}
    processing.erase(find(processing.begin(), processing.end(), s));
  }
  answer.push_back(central);

  return answer;
}

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