#685478 (C++17) No.901 K-ary εxtrεεmε

提出ソース

結果

問題	No.901 K-ary εxtrεεmε
ユーザー	李袁忠
提出日時	2021-08-02 22:55:57
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	367 ms / 3,000 ms
コード長	7,425 bytes
コンパイル時間	5,822 ms
コンパイル使用メモリ	231,352 KB
実行使用メモリ	53,708 KB
最終ジャッジ日時	2023-10-14 20:59:14
合計ジャッジ時間	17,432 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	233 ms 53,708 KB
testcase_01	AC	1 ms 4,352 KB
testcase_02	AC	3 ms 4,352 KB
testcase_03	AC	4 ms 4,348 KB
testcase_04	AC	3 ms 4,348 KB
testcase_05	AC	3 ms 4,352 KB
testcase_06	AC	4 ms 4,352 KB
testcase_07	AC	319 ms 50,456 KB
testcase_08	AC	319 ms 50,500 KB
testcase_09	AC	319 ms 50,424 KB
testcase_10	AC	329 ms 50,408 KB
testcase_11	AC	331 ms 50,372 KB
testcase_12	AC	341 ms 50,452 KB
testcase_13	AC	337 ms 50,220 KB
testcase_14	AC	339 ms 50,388 KB
testcase_15	AC	342 ms 50,352 KB
testcase_16	AC	350 ms 50,288 KB
testcase_17	AC	298 ms 50,568 KB
testcase_18	AC	301 ms 50,284 KB
testcase_19	AC	301 ms 50,336 KB
testcase_20	AC	299 ms 50,260 KB
testcase_21	AC	296 ms 50,344 KB
testcase_22	AC	360 ms 50,376 KB
testcase_23	AC	367 ms 50,260 KB
testcase_24	AC	363 ms 50,312 KB
testcase_25	AC	364 ms 50,296 KB
testcase_26	AC	366 ms 50,484 KB
testcase_27	AC	206 ms 50,424 KB
testcase_28	AC	211 ms 50,456 KB
testcase_29	AC	212 ms 50,364 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// #define LOCAL
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,s,n) for (int i = (ll)s; i < (ll)n; i++)
#define rrep(i,n,e) for (int i = (ll)n; i > (ll)e; i--)
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
// #define M_PI 3.14159265358979323846 // CF
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()
#define Decimal(x) cout << fixed << setprecision(10) << x << endl; // print Decimal number 10 Rank
#define endl "\n"
#define Case(x) printf("Case #%d: ", x); // gcj

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
typedef vector<PI> vpi;
typedef vector<vector<PI>> vvpi;
typedef vector<PLL> vpl;
typedef vector<vector<PLL>> vvpl;
typedef vector<char> vch;
typedef vector<vector<char>> vvch;

constexpr ll INF = 1001002003004005006ll;
constexpr int n_max = 2e5+10;

template<class T>
inline bool chmax(T &a, T b) { if(a<b) { a=b; return true; } return false; };
template<class T>
inline bool chmin(T &a, T b) { if(a>b) { a=b; return true; } return false; };

template<class T, class U>
T POW(T x, U n) {T ret=1; while (n>0) {if (n&1) {ret*=x;} x*=x; n>>=1;} return ret;};

// debug
template <typename A, typename B>
string to_string(pair<A, B> p);
string to_string(const string &s) {return '"' + s + '"';};
string to_string(const char c) {return to_string((string) &c);};
string to_string(bool b) {return (b ? "true" : "false");};
// string to_string(mint m) {return to_string(m.a); };
template <size_t N>
string to_string(bitset<N> v){
  string res = "";
  for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);
  return res;
};
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for(const auto &x : v) {
    if(!first) res += ", ";
    first = false; res += to_string(x);
  }
  res += "}";
  return res;
};
template <typename A, typename B>
string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}

void debug_out() {cerr << endl;};
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); };

void LINE_OUT() { cout << "--------------" << endl; };
void SPACE_OUT() { cout << endl; };

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define LINE LINE_OUT();
#define SPACE SPACE_OUT();
#else
#define debug(...) 71
#define LINE 71;
#define SPACE 71;
#endif

void print() { cout << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  cout << head;
  if (sizeof...(tail) != 0) cout << " ";
  print(forward<Tail>(tail)...);
};

template <class T>
void print(vector<T> &vec) {
  for (auto& a : vec) {
    cout << a;
    if (&a != &vec.back()) cout << " ";
  }
  cout << endl;
};

template <class T>
void print(vector<vector<T>> &df) {
  for (auto& vec : df) { print(vec); }
};

// <to, cost>
class LCA {
public:
  int V, logV; // V: node num
  vector<int> depth, dist;
  vector<vector<int>> parent; // parent[k][v], go back 2^k
  vector<vector<pair<int,int>>> tree;

  LCA(vector<vector<pair<int,int>>> in_tree) {
    tree = in_tree;
    V = in_tree.size();
    logV = 0;
    while (V > (1LL<<logV)) logV++;
    this->depth = vector<int>(V);
    this->dist = vector<int>(V);
    this->parent = vector<vector<int>>(logV, vector<int>(V));
  }

  void dfs(int u, int p, int d, int c) { // dfs: calculate dist and parent
    depth[u] = d;
    parent[0][u] = p;
    dist[u] = c;
    for (int i = 0; i < (int)tree[u].size(); i++) {
      int v = tree[u][i].first;
      int cost = tree[u][i].second;
      if (v == p) continue;
      dfs(v, u, d+1, c + cost);
    }
  }

  void doubling() { // doubling: build parent
    for (int k = 0; k < logV-1; k++) {
      for (int v = 0; v < V; v++) {
        if (parent[k][v] < 0) parent[k+1][v] = -1;
        else parent[k+1][v] = parent[k][parent[k][v]];
      }
    }
  }

  void build(int u = 0, int p = -1, int d = 0, int c = 0) {
    dfs(u,p,d,c);
    doubling();
  }

  int query(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int k = 0; k < logV; k++) {
      if ((depth[v] - depth[u]) >> k & 1) v = parent[k][v];
    }
    if (u == v) return u;

    for (int k = logV-1; k >= 0; k--) {
      if (parent[k][u] != parent[k][v]) {
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    return parent[0][u];
  }

  int get_distance(int u, int v) {
    int lca = query(u, v);
    return dist[u] + dist[v] - 2 * dist[lca];
  }
};

class AuxiliaryTree {
public:
  int V;
  vector<vector<pair<int,int>>> tree;
  vector<int> in, out;
  LCA lca;

  vector<vector<pair<int,int>>> T; // auxiliary_tree graph

  AuxiliaryTree(vector<vector<pair<int,int>>> in_tree): lca(in_tree) {
    this->V = in_tree.size();
    this->tree = in_tree;
    lca.build();

    this->in = vector<int>(V);
    this->out = vector<int>(V);
    int cur_in = 0, cur_out = 0;
    et_dfs(0,-1,cur_in, cur_out);

    this->T = vector<vector<pair<int,int>>>(V);
  }

  void et_dfs(int u, int p, int &cur_in, int &cur_out) { // Euler tour
    in[u] = cur_in++;
    for (auto pi: tree[u]) {
      int v = pi.first;
      if (v == p) continue;
      et_dfs(v, u, cur_in, cur_out);
    }
    out[u] = cur_out++;
  }

  void add_aux_edge(int u, int v) {
    int d = lca.get_distance(u, v);
    T[u].push_back(make_pair(v, d));
    T[v].push_back(make_pair(u, d));
  }

  int query(vector<int> &vs) {
    sort(vs.begin(), vs.end(), [&](int u, int v) { return in[u]<in[v]; });
    vs.erase(unique(vs.begin(),vs.end()),vs.end());

    int K = vs.size();
    for (int i=0; i < K-1; i++) vs.push_back(lca.query(vs[i], vs[i+1]));
    sort(vs.begin(), vs.end(), [&](int u, int v) { return in[u]<in[v]; });
    vs.erase(unique(vs.begin(),vs.end()),vs.end());

    vector<int> stack;
    for (int v: vs) T[v].clear();
    for (int v: vs) {
      while (!stack.empty() && out[stack.back()] < in[v]) {
        int last = stack.back(); stack.pop_back();
        if (!stack.empty()) add_aux_edge(last, stack.back()); // child add parent
      }

      if (!stack.empty()) add_aux_edge(stack.back(), v); // parent add child
      stack.push_back(v);
    }

    int last = stack.back(); stack.pop_back();
    while (!stack.empty()) {
      add_aux_edge(last, stack.back()); // child add parent
      last = stack.back(); stack.pop_back();
    }

    return last; // return root
  }
};

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int N; cin >> N;
  vvpi G(N);
  rep(i,0,N-1) {
    int u, v, w; cin >> u >> v >> w;
    G[u].pb({v, w});
    G[v].pb({u, w});
  }

  AuxiliaryTree aux(G);


  int Q; cin >> Q;
  while (Q--) {
    int K; cin >> K;
    vi vs(K);
    rep(i,0,K) { cin >> vs[i]; }
    aux.query(vs);
    int ans = 0;
    K = vs.size();
    rep(i,0,K) {
      int u = vs[i], v = vs[(i+1)%K];
      ans += aux.lca.get_distance(u, v);
    }
    ans /= 2;
    cout << ans << endl;
  }

  return 0;
};

yukicoder

結果

テストケース

ソースコード