제출 #564152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
564152		hoanghq2004	즐거운 행로 (APIO20_fun)	C++14	컴파일 에러	0 ms	0 KiB

fun

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#define Submit
#ifdef Submit
#include "fun.h"

#endif // Submit

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(std :: chrono :: system_clock :: now().time_since_epoch().count());

#ifndef Submit

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

#endif // Submit

const int N = 1e5 + 10;

int n;
int d[N];
vector <pair <int, int> > s[3];

vector <int> createFunTour(int _n, int _) {
    n = _n;
    int c = 0;
    int minsz = 1e9;
    for (int i = 0; i < n; ++i) {
        int sz = attractionsBehind(0, i);
        if (sz >= (n + 1) / 2 && sz < minsz) {
            minsz = sz;
            c = i;
        }
    }
    vector <int> branches;
    for (int i = 0; i < n; ++i) d[i] = hoursRequired(i, c);
    for (int i = 0; i < n; ++i) if (d[i] == 1) branches.push_back(i);
    for (int i = 0; i < n; ++i) {
        if (i == c) continue;
        int found = 0;
        for (int j = 0; j < branches.size() - 1; ++j) {
            if (hoursRequired(i, branches[j]) + 1 == d[i]) {
                s[j].push_back({d[i], i});
                found = 1;
                break;
            }
        }
//        if (i == 4) cout << found << "afdsdf\n";
        if (!found) s[branches.size() - 1].push_back({d[i], i});

    }
    for (int i = 0; i < branches.size(); ++i) sort(s[i].begin(), s[i].end());
    vector <int> ans;
    int cur_branch = -1;
//    for (int i = 0; i < branches.size(); ++i) {
//        for (auto x: s[i]) cout << i << ' ' << x.first << ' ' << x.second << "aaa\n";
//    }
    for (int T = 0; T + 1 < n; ++T) {
        int maxsz = 0, b = 0, tot = 0;
        pair <int, int> farthest = {-1, -1};
        for (int i = 0; i < branches.size(); ++i) {
            if (s[i].size() > maxsz) {
                maxsz = s[i].size();
                b = i;
            }
            tot += s[i].size();
        }
        if (maxsz * 2 >= tot) {
            int cur = 0; // 0/1: b/ small
            int szbig = maxsz, szsmall = tot - szbig;
            if (cur_branch == -1 || szbig != szsmall) {
                cur = (szbig < szsmall);
            } else {
                int othersmall = -1;
                for (int i = 0; i < branches.size(); ++i)
                    if (i != cur_branch && i != b) othersmall = i;
                assert(othersmall != -1);
                if (s[othersmall].size() && s[othersmall].back().first > d[ans.back()]) {
                    ans.push_back(s[othersmall].back().second);
                    s[othersmall].pop_back();
                }
                cur = 0;
            }
            vector <pair <int, int> > p[2];
            p[0] = s[b];
            for (int i = 0; i < branches.size(); ++i)
                if (i != b) {
                    for (auto x: s[i]) p[1].push_back(x);
                }
            sort(p[1].begin(), p[1].end());
            while (p[0].size() || p[1].size()) {
                ans.push_back(p[cur].back().second);
                p[cur].pop_back();
                cur ^= 1;
            }
            break;
        }
        for (int i = 0; i < branches.size(); ++i) {
            if (i == cur_branch) continue;
            if (s[i].size()) farthest = max(farthest, make_pair(s[i].back().first, i));
        }
        int i = farthest.second;
        ans.push_back(s[i].back().second);
        s[i].pop_back();
    }
    ans.push_back(c);
    return ans;
}

#ifndef Submit

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 // Submit

/*
9 100000
0 1
1 2
1 3
3 4
4 6
6 5
6 7
7 8
*/

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

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:181:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |         for (int j = 0; j < branches.size() - 1; ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
fun.cpp:192:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |     for (int i = 0; i < branches.size(); ++i) sort(s[i].begin(), s[i].end());
      |                     ~~^~~~~~~~~~~~~~~~~
fun.cpp:201:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |         for (int i = 0; i < branches.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~~~
fun.cpp:202:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  202 |             if (s[i].size() > maxsz) {
      |                 ~~~~~~~~~~~~^~~~~~~
fun.cpp:215:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |                 for (int i = 0; i < branches.size(); ++i)
      |                                 ~~^~~~~~~~~~~~~~~~~
fun.cpp:226:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |             for (int i = 0; i < branches.size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~~
fun.cpp:238:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  238 |         for (int i = 0; i < branches.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccusHENj.o: in function `hoursRequired(int, int)':
grader.cpp:(.text+0x2d0): multiple definition of `hoursRequired(int, int)'; /tmp/cccOp5Xg.o:fun.cpp:(.text+0x9e0): first defined here
/usr/bin/ld: /tmp/ccusHENj.o: in function `attractionsBehind(int, int)':
grader.cpp:(.text+0x3d0): multiple definition of `attractionsBehind(int, int)'; /tmp/cccOp5Xg.o:fun.cpp:(.text+0xac0): first defined here
/usr/bin/ld: /tmp/ccusHENj.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cccOp5Xg.o:fun.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status