Submission #2965871


Source Code Expand

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll INF = (1LL<<60);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class LCA {
public:
  const int n = 0;
  const int log2_n = 0;
  VVI par;
  vector<vector<PII>> g;
  VI depth, d;

  // parとdを構築する
  void dfs(int v, int p, int dist, int n_depth) {
    par[0][v] = p; d[v] = dist; depth[v] = n_depth;
    for (auto e : g[v]) {
      if (e.first != p) dfs(e.first, v, dist + e.second, n_depth+1);
    }
  }

  LCA(int n_=1e5) :
    n(n_), log2_n(log2(n)+1), par(log2_n, VI(n)), g(n, vector<PII>()), depth(n), d(n) {}
  // u-vに重みcostの辺を張る
  void add_edge(int u, int v, int cost) { g[u].PB({v, cost}); g[v].PB({u, cost}); }
  // rootを根としてparとdを構築
  void build(int root = 0) {
    dfs(root, -1, 0, 0);
    REP(k, log2_n-1) {
      REP(v, n) {
        if(par[k][v] < 0) par[k+1][v] = -1;
        else par[k+1][v] = par[k][par[k][v]];
      }
    }
  }
  // uとvのlcaを返す
  int get(int u, int v) {
    if (depth[u] > depth[v]) std::swap(u, v);
    for (int k = 0; k < log2_n; k++) {
      if ((depth[v] - depth[u]) >> k & 1) {
        v = par[k][v];
      }
    }
    if (u == v) return u;
    for (int k = log2_n - 1; k >= 0; k--) {
      if (par[k][u] != par[k][v]) {
        u = par[k][u];
        v = par[k][v];
      }
    }
    return par[0][u];
  }
  // uとvの距離を返す
  int length(int u, int v) {
    int lca = get(u, v);
    return d[u] + d[v] - 2*d[lca];
  }
};

VI g[100010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;
  LCA lca(n);
  REP(i, n-1) {
    int a, b; cin >> a >> b; a--, b--;
    g[a].PB(b);
    g[b].PB(a);
    lca.add_edge(a, b, 1);
  }
  lca.build();

  // オイラーツアー
  int cnt1 = 0, cnt2 = 0;
  vector<PII> idx(n);
  function<void(int,int)> dfs = [&](int x, int p) {
    idx[x].first = cnt1++;
    for(int i: g[x]) {
      if(i == p) continue;
      dfs(i, x);
    }
    idx[x].second = cnt2++;
  };
  dfs(0, -1);

  // cout << idx << endl;

  int q;
  cin >> q;
  VI ans(q);
  REP(i, q) {
    int m, k;
    cin >> m >> k;
    vector<PII> v(m);
    REP(j, m) {
      cin >> v[j].second, v[j].second--;
      v[j].first = idx[v[j].second].first;
    }
    // cout << v << endl;
    sort(ALL(v));
    int ret = 0;
    REP(j, m-k+1) {
      // v[j] と v[j+k-1] のLCAを取る
      chmax(ret, lca.depth[lca.get(v[j].second, v[j+k-1].second)]);
      // cout << lca.get(v[j].second, v[j+k-1].second) << "," << lca.depth[lca.get(v[j].second, v[j+k-1].second)] << " ";
    }
    // cout << endl;
    ans[i] = ret;
  }

  REP(i, q) cout << ans[i] << endl;

  return 0;
}

Submission Info

Submission Time
Task F - 根付き木のみさわさん
User ferin_tech
Language C++14 (GCC 5.4.1)
Score 130
Code Size 3684 Byte
Status AC
Exec Time 278 ms
Memory 39280 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 20 / 20 110 / 110
Status
AC × 3
AC × 29
AC × 55
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt
Subtask2 sample_01.txt, sample_02.txt, sample_03.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_15.txt, subtask_02_16.txt, subtask_02_17.txt, subtask_02_18.txt, subtask_02_19.txt, subtask_02_20.txt, subtask_02_21.txt, subtask_02_22.txt, subtask_02_23.txt, subtask_02_24.txt, subtask_02_25.txt, subtask_02_26.txt
Case Name Status Exec Time Memory
sample_01.txt AC 6 ms 2944 KB
sample_02.txt AC 2 ms 2560 KB
sample_03.txt AC 2 ms 2560 KB
subtask_01_01.txt AC 2 ms 2560 KB
subtask_01_02.txt AC 2 ms 2560 KB
subtask_01_03.txt AC 2 ms 2688 KB
subtask_01_04.txt AC 3 ms 2688 KB
subtask_01_05.txt AC 23 ms 2688 KB
subtask_01_06.txt AC 2 ms 2688 KB
subtask_01_07.txt AC 3 ms 2688 KB
subtask_01_08.txt AC 22 ms 2688 KB
subtask_01_09.txt AC 2 ms 2688 KB
subtask_01_10.txt AC 3 ms 2688 KB
subtask_01_11.txt AC 21 ms 2688 KB
subtask_01_12.txt AC 2 ms 2688 KB
subtask_01_13.txt AC 3 ms 2688 KB
subtask_01_14.txt AC 22 ms 2688 KB
subtask_01_15.txt AC 2 ms 2688 KB
subtask_01_16.txt AC 3 ms 2688 KB
subtask_01_17.txt AC 22 ms 2688 KB
subtask_01_18.txt AC 2 ms 2688 KB
subtask_01_19.txt AC 3 ms 2688 KB
subtask_01_20.txt AC 22 ms 2688 KB
subtask_01_21.txt AC 2 ms 2688 KB
subtask_01_22.txt AC 3 ms 2688 KB
subtask_01_23.txt AC 22 ms 2688 KB
subtask_01_24.txt AC 2 ms 2688 KB
subtask_01_25.txt AC 3 ms 2688 KB
subtask_01_26.txt AC 22 ms 2688 KB
subtask_02_01.txt AC 99 ms 32624 KB
subtask_02_02.txt AC 106 ms 31472 KB
subtask_02_03.txt AC 124 ms 31344 KB
subtask_02_04.txt AC 96 ms 33008 KB
subtask_02_05.txt AC 96 ms 31728 KB
subtask_02_06.txt AC 114 ms 31600 KB
subtask_02_07.txt AC 104 ms 35440 KB
subtask_02_08.txt AC 109 ms 34416 KB
subtask_02_09.txt AC 129 ms 34160 KB
subtask_02_10.txt AC 100 ms 32368 KB
subtask_02_11.txt AC 108 ms 30960 KB
subtask_02_12.txt AC 129 ms 30960 KB
subtask_02_13.txt AC 121 ms 31856 KB
subtask_02_14.txt AC 119 ms 30960 KB
subtask_02_15.txt AC 135 ms 30704 KB
subtask_02_16.txt AC 103 ms 39280 KB
subtask_02_17.txt AC 107 ms 38256 KB
subtask_02_18.txt AC 133 ms 38000 KB
subtask_02_19.txt AC 103 ms 31856 KB
subtask_02_20.txt AC 145 ms 30704 KB
subtask_02_21.txt AC 152 ms 30448 KB
subtask_02_22.txt AC 150 ms 36464 KB
subtask_02_23.txt AC 142 ms 38128 KB
subtask_02_24.txt AC 165 ms 34160 KB
subtask_02_25.txt AC 278 ms 31344 KB
subtask_02_26.txt AC 274 ms 39152 KB