Submission #2967359


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

// Binary Indexed Tree
// 0-indexed
template <typename T>
class BIT {
private:
  // データ
  vector<T> bit;
  // 単位元, 要素数
  int neutral = 0;
  // 更新クエリ, 区間クエリ
  function<T(T,T)> f = [](const T l, const T r) -> T { return l+r; },
                   g = [](const T l, const T r) -> T { return l+r; };
public:
  // 初期化
  BIT(int n_ = 1e5) { init(n_); }
  void init(int n_ = 1e5) { bit.assign(n_+1, neutral); }
  // iに対する点更新クエリ
  void update(int i, T w) {
    for(int x = i+1; x < bit.size(); x += x&-x) bit[x] = f(bit[x], w);
  }
  // [0,i)に対する区間クエリ
  T query(int i) {
    T ret = neutral;
    for(int x = i+1; x > 0; x -= x & -x) ret = g(ret, bit[x]);
    return ret;
  }
};

template <typename S>
class sparseTable {
public:
  using T = typename S::T;
  int n;
  vector<int> log2;
  vector<vector<T>> t;

  sparseTable(int nn = 1e5) { init(nn); }
  void init(int nn) {
    n = nn;
    log2.assign(n+1, 0);
    for(int i=2; i<=n; ++i) log2[i] = log2[i >> 1] + 1;
    t.assign(log2[n]+1, vector<T>(n));
  }
  void build(vector<T> v) {
    for(int i=0; i<n; ++i) t[0][i] = v[i];
    for(int j=1; j<=log2[n]; ++j) {
      int w = 1LL<<(j-1);
      for (int i = 0; i+(w<<1) <= n; ++i) {
        t[j][i] = S::op(t[j-1][i], t[j-1][i+w]);
      }
    }
  }
  // [l, r]
  T query(int l, int r) {
    int j = log2[r - l];
    return S::op(t[j][l], t[j][r-(1 << j)+1]);
  }
};
struct minimum {
  using T = PII;
  static T op(const T& a, const T& b) { return min(a, b); }
};

struct LCA {
  struct edge { int id, to, cost; };
  const int n = 0;
  const int log2_n = 0;
  VVI par;
  vector<vector<edge>> g;
  VI depth;     // 頂点iの深さ
  VI vs;        // 頂点を訪問順に並べたもの
  VI depth_seq; // depth_seq[i] = (頂点vs[i]の深さ)
  VI id;        // 頂点が初めてvsに登場するインデックス
  VI es;        // 辺のインデックス(i*2+(葉方向:0,根方向:1))
  VI w;         // 辺の重み
  BIT<int> bit;
  sparseTable<minimum> st;

  void dfs(int v, int p, int d, int &k) {
    // cout << v << " " << p << " " << d << " " << k << endl;
    id[v] = k; vs[k] = v; depth_seq[k++] = d; depth[v] = d;
    for(auto e: g[v]) {
      if(e.to == p) continue;
      bit.update(k, e.cost); es[e.id*2] = k;
      // cout << k << " " << e.to << " " << e.cost << endl;
      dfs(e.to, v, d+1, k);
      vs[k] = v; depth_seq[k++] = d;
      bit.update(k, -e.cost); es[e.id*2+1] = k;
      // cout << k << " " << e.to << " " << -e.cost  << endl;
    }
  }

  LCA(int n_=1e5) :
    n(n_), g(n, vector<edge>()), depth(n), vs(2*n-1),
    depth_seq(2*n-1), id(n), es((n-1)*2), w(n-1)
  {
    bit.init(2*n-1);
  }
  // u-vに重みcostのi番目の辺を張る
  void add_edge(int i, int u, int v, int cost) {
    g[u].PB({i, v, cost});
    g[v].PB({i, u, cost});
  }
  // rootを根として初期化
  void build(int root = 0) {
    int k = 0;
    dfs(root, -1, 0, k);
    // REP(i, 2*n-1) cout << bit.query(i) << " ";
    // cout << endl;
    // RMQの初期化
    vector<PII> v(2*n-1);
    REP(i, 2*n-1) v[i] = {depth_seq[i], i};
    // cout << vs << endl;
    // cout << depth_seq << endl;
    st.init(2*n-1);
    st.build(v);
  }

  // uとvのlcaを返す
  int get(int u, int v) {
    if(id[u] > id[v]) swap(u, v);
    return vs[st.query(id[u], id[v]).second];
  }
  // uとvの距離を返す
  int length(int u, int v) {
    int lca = get(u, v);
    // cout << "vertex:" << u << " " << v << " " << lca << endl;
    // cout << "id=" << id[u] << "," << id[v] << "," << id[lca] << endl;
    // cout << bit.query(id[u])-bit.query(id[lca]) << " " << bit.query(id[v])-bit.query(id[lca]) << endl;
    return bit.query(id[v]) + bit.query(id[u]) - 2*bit.query(id[lca]);
  }
  // 辺xのコストをtに変更
  void update(int x, int t) {
    bit.update(es[x*2], t - w[x]);
    bit.update(es[x*2+1], w[x] - t);
    w[x] = t;
  }
};

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(i, 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);
  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;
    }
    sort(ALL(v));
    int ret = 0;
    REP(j, m-k+1) {
      // v[j] と v[j+k-1] のLCAを取る
      chmax(ret, lca.length(lca.get(v[j].second, v[j+k-1].second), 0));
      // cout << lca.get(v[j].second, v[j+k-1].second) << "," << lca.depth[lca.get(v[j].second, v[j+k-1].second)] << endl;
    }
    // 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 6285 Byte
Status AC
Exec Time 349 ms
Memory 124100 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 16 ms 32384 KB
sample_02.txt AC 16 ms 32384 KB
sample_03.txt AC 16 ms 32384 KB
subtask_01_01.txt AC 16 ms 32256 KB
subtask_01_02.txt AC 16 ms 32256 KB
subtask_01_03.txt AC 16 ms 32384 KB
subtask_01_04.txt AC 16 ms 32384 KB
subtask_01_05.txt AC 36 ms 32384 KB
subtask_01_06.txt AC 16 ms 32384 KB
subtask_01_07.txt AC 16 ms 32384 KB
subtask_01_08.txt AC 35 ms 32384 KB
subtask_01_09.txt AC 16 ms 32384 KB
subtask_01_10.txt AC 17 ms 32384 KB
subtask_01_11.txt AC 35 ms 32384 KB
subtask_01_12.txt AC 16 ms 32384 KB
subtask_01_13.txt AC 16 ms 32384 KB
subtask_01_14.txt AC 35 ms 32384 KB
subtask_01_15.txt AC 16 ms 32384 KB
subtask_01_16.txt AC 16 ms 32384 KB
subtask_01_17.txt AC 35 ms 32384 KB
subtask_01_18.txt AC 16 ms 32384 KB
subtask_01_19.txt AC 16 ms 32384 KB
subtask_01_20.txt AC 36 ms 32384 KB
subtask_01_21.txt AC 16 ms 32384 KB
subtask_01_22.txt AC 16 ms 32384 KB
subtask_01_23.txt AC 36 ms 32384 KB
subtask_01_24.txt AC 16 ms 32384 KB
subtask_01_25.txt AC 16 ms 32384 KB
subtask_01_26.txt AC 35 ms 32384 KB
subtask_02_01.txt AC 158 ms 115780 KB
subtask_02_02.txt AC 161 ms 115780 KB
subtask_02_03.txt AC 180 ms 115780 KB
subtask_02_04.txt AC 158 ms 115396 KB
subtask_02_05.txt AC 158 ms 115396 KB
subtask_02_06.txt AC 174 ms 115396 KB
subtask_02_07.txt AC 156 ms 119236 KB
subtask_02_08.txt AC 167 ms 119236 KB
subtask_02_09.txt AC 193 ms 119236 KB
subtask_02_10.txt AC 158 ms 115268 KB
subtask_02_11.txt AC 156 ms 115268 KB
subtask_02_12.txt AC 181 ms 115268 KB
subtask_02_13.txt AC 173 ms 114500 KB
subtask_02_14.txt AC 174 ms 114500 KB
subtask_02_15.txt AC 188 ms 114500 KB
subtask_02_16.txt AC 169 ms 124100 KB
subtask_02_17.txt AC 164 ms 124100 KB
subtask_02_18.txt AC 188 ms 124100 KB
subtask_02_19.txt AC 164 ms 114500 KB
subtask_02_20.txt AC 172 ms 114500 KB
subtask_02_21.txt AC 189 ms 114500 KB
subtask_02_22.txt AC 178 ms 120388 KB
subtask_02_23.txt AC 183 ms 123588 KB
subtask_02_24.txt AC 209 ms 119108 KB
subtask_02_25.txt AC 349 ms 114500 KB
subtask_02_26.txt AC 343 ms 124100 KB