Submission #2225738


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define _p(...) (void)printf(__VA_ARGS__)
#define forr(x,arr) for(auto&& x:arr)
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) _rep3(i,0,n)
#define _rep3(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)
#define _rrep2(i,n) _rrep3(i,0,n)
#define _rrep3(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define bit(n) (1LL<<(n))
#define sz(x) ((int)(x).size())
#define fst first
#define snd second

string DBG_DLM(int &i){return(i++==0?"":", ");}
#define DBG_B(exp){int i=0;os<<"{";{exp;}os<<"}";return os;}
template<class T>ostream&operator<<(ostream&os,vector<T>v);
template<class T>ostream&operator<<(ostream&os,set<T>v);
template<class T>ostream&operator<<(ostream&os,queue<T>q);
template<class T>ostream&operator<<(ostream&os,priority_queue<T>q);
template<class T,class K>ostream&operator<<(ostream&os,pair<T,K>p);
template<class T,class K>ostream&operator<<(ostream&os,map<T,K>mp);
template<class T,class K>ostream&operator<<(ostream&os,unordered_map<T,K>mp);
template<int I,class TPL>void DBG(ostream&os,TPL t){}
template<int I,class TPL,class H,class...Ts>void DBG(ostream&os,TPL t){os<<(I==0?"":", ")<<get<I>(t);DBG<I+1,TPL,Ts...>(os,t);}
template<class T,class K>void DBG(ostream&os,pair<T,K>p,string delim){os<<"("<<p.first<<delim<<p.second<<")";}
template<class...Ts>ostream&operator<<(ostream&os,tuple<Ts...>t){os<<"(";DBG<0,tuple<Ts...>,Ts...>(os,t);os<<")";return os;}
template<class T,class K>ostream&operator<<(ostream&os,pair<T,K>p){DBG(os,p,", ");return os;}
template<class T>ostream&operator<<(ostream&os,vector<T>v){DBG_B(forr(t,v){os<<DBG_DLM(i)<<t;});}
template<class T>ostream&operator<<(ostream&os,set<T>s){DBG_B(forr(t,s){os<<DBG_DLM(i)<<t;});}
template<class T>ostream&operator<<(ostream&os,queue<T>q){DBG_B(for(;q.size();q.pop()){os<<DBG_DLM(i)<<q.front();});}
template<class T>ostream&operator<<(ostream&os,priority_queue<T>q){DBG_B(for(;q.size();q.pop()){os<<DBG_DLM(i)<<q.top();});}
template<class T,class K>ostream&operator<<(ostream&os,map<T,K>m){DBG_B(forr(p,m){os<<DBG_DLM(i);DBG(os,p,"->");});}
template<class T,class K>ostream&operator<<(ostream&os,unordered_map<T,K>m){DBG_B(forr(p,m){os<<DBG_DLM(i);DBG(os,p,"->");});}
#define DBG_OVERLOAD(_1,_2,_3,_4,_5,_6,macro_name,...)macro_name
#define DBG_LINE(){char s[99];sprintf(s,"line:%3d | ",__LINE__);cerr<<s;}
#define DBG_OUTPUT(v){cerr<<(#v)<<"="<<(v);}
#define DBG1(v,...){DBG_OUTPUT(v);}
#define DBG2(v,...){DBG_OUTPUT(v);cerr<<", ";DBG1(__VA_ARGS__);}
#define DBG3(v,...){DBG_OUTPUT(v);cerr<<", ";DBG2(__VA_ARGS__);}
#define DBG4(v,...){DBG_OUTPUT(v);cerr<<", ";DBG3(__VA_ARGS__);}
#define DBG5(v,...){DBG_OUTPUT(v);cerr<<", ";DBG4(__VA_ARGS__);}
#define DBG6(v,...){DBG_OUTPUT(v);cerr<<", ";DBG5(__VA_ARGS__);}
#define DEBUG0(){DBG_LINE();cerr<<endl;}
#ifdef LOCAL
#define out(...){DBG_LINE();DBG_OVERLOAD(__VA_ARGS__,DBG6,DBG5,DBG4,DBG3,DBG2,DBG1)(__VA_ARGS__);cerr<<endl;}
#else
#define out(...)
#endif

using ll=long long;
using pii=pair<int,int>;using pll=pair<ll,ll>;using pil=pair<int,ll>;using pli=pair<ll,int>;
using vs=vector<string>;using vvs=vector<vs>;using vvvs=vector<vvs>;
using vb=vector<bool>;using vvb=vector<vb>;using vvvb=vector<vvb>;
using vi=vector<int>;using vvi=vector<vi>;using vvvi=vector<vvi>;
using vl=vector<ll>;using vvl=vector<vl>;using vvvl=vector<vvl>;
using vd=vector<double>;using vvd=vector<vd>;using vvvd=vector<vvd>;
using vpii=vector<pii>;using vvpii=vector<vpii>;using vvvpii=vector<vvpii>;
template<class T>bool amax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>bool amin(T&a,const T&b){return a>b?a=b,1:0;}
ll ri(){ll l;cin>>l;return l;} string rs(){string s;cin>>s;return s;}

struct HLDecomposition {
  using Edge = int;
  using Graph = vector<vector<Edge>>;

  const int n;
  const Graph &G;
  vector<int> vid, head, heavy, parent, depth, inv;

  HLDecomposition(const Graph &G, const int root = 0) : n(G.size()), G(G), vid(n, -1), head(n), heavy(n, -1), parent(n), depth(n), inv(n) {
    dfs(root, -1);
    bfs(root);
  }

  void for_each(int u, int v, function<void(int, int)> f) {
    if (vid[u] > vid[v]) swap(u, v);
    f(max(vid[head[v]], vid[u]), vid[v]);
    if (head[u] != head[v]) for_each(u, parent[head[v]], f);
  }

  private:
  int dfs(int cur, int pre) {
    parent[cur] = pre;
    int size = 1;
    int max_size = 0;
    for (auto nex : G[cur]) if (nex != pre) {
      depth[nex] = depth[cur] + 1;
      int nex_size = dfs(nex, cur);
      size += nex_size;
      if (max_size < nex_size) max_size = nex_size, heavy[cur] = nex;
    }
    return size;
  }

  void bfs(int root) {
    int k = 0;
    queue<int> q({ root });
    while (!q.empty()) {
      int h = q.front(); q.pop();
      for (int i = h; i != -1; i = heavy[i]) {
        vid[i] = k++;
        inv[vid[i]] = i;
        head[i] = h;
        for (int j : G[i]) if (j != parent[i] && j != heavy[i]) q.push(j);
      }
    }
  }
};

template <class V = int, bool MAX = true> struct SegmentTree_RAQ_RMQ {
  struct Node {
    V dat;
    V lazy;
    Node() : dat(0), lazy(0) {}
  };

  const int n;
  vector<Node> seg;
  SegmentTree_RAQ_RMQ(int size) : n(1 << (32 - __builtin_clz(size - 1))), seg(n * 2) {};

  void set(int i, const V v) { seg[i + n] = v; }

  void build() {
    for (int i = n - 1; i > 0; i--) seg[i] = merge(seg[i * 2].dat, seg[i * 2 + 1].dat);
  }

  void update(int begin, int end, V val) { update_range_rec(1, 0, n, begin, end, val); }

  V query(int begin, int end) { return query_rec(1, 0, n, begin, end); }

private:
  V merge(const V l, const V r) { return MAX ? max(l, r) : min(l, r); }

  void propagate(int node, int l, int r) {
    seg[node].dat += seg[node].lazy;
    if (r - l > 1) {
      seg[node * 2 + 0].lazy += seg[node].lazy;
      seg[node * 2 + 1].lazy += seg[node].lazy;
    }
    seg[node].lazy = 0;
  }

  void update_range_rec(int node, int l, int r, int qbegin, int qend, V val) {
    propagate(node, l, r);
    if (r <= qbegin || qend <= l) {
      return;
    }
    if (qbegin <= l && r <= qend) {
      seg[node].lazy = val;
      propagate(node, l, r);
    }
    else {
      int m = (l + r) >> 1;
      update_range_rec(2 * node + 0, l, m, qbegin, qend, val);
      update_range_rec(2 * node + 1, m, r, qbegin, qend, val);
      seg[node].dat = merge(seg[2 * node].dat, seg[2 * node + 1].dat);
    }
  }

  V query_rec(int node, int l, int r, int qbegin, int qend) {
    propagate(node, l, r);
    if (qbegin <= l && r <= qend) {
      return seg[node].dat;
    }
    if (r <= qbegin || qend <= l) {
      return MAX ? numeric_limits<V>::min() : numeric_limits<V>::max();
    }
    int m = (l + r) >> 1;
    return merge(query_rec(2 * node, l, m, qbegin, qend), query_rec(2 * node + 1, m, r, qbegin, qend));
  }
};


void Main() {
  int n = ri();
  vvi E(n);
  rep(i, n-1) {
    int u = ri() - 1;
    int v = ri() - 1;
    E[u].push_back(v);
    E[v].push_back(u);
  }

  HLDecomposition hld(E);
  SegmentTree_RAQ_RMQ<int> seg(n);

  int q = ri();
  while (q--) {
    int m = ri();
    int k = ri();
    vi V(m);
    rep(i, m) {
      int v = V[i] = ri() - 1;

      auto add = [&](int l, int r) {
        seg.update(l, r+1, 1);
      };
      hld.for_each(0, v, add);
    }

    int ans = 0;
    forr(v, V) {
      auto f = [&](int l, int r) {
        if (seg.query(l, l+1) < k) return;
        int ok = l;
        int ng = r+1;

        auto check = [&](int x) -> bool {
          return seg.query(x, x+1) >= k;
        };

        while (abs(ok - ng) > 1) {
          int mid = (ok + ng) / 2;
          bool c = check(mid);
          if (c) ok = mid;
          else ng = mid;
        }

        int x = hld.inv[ok];
        amax(ans, hld.depth[x]);
      };
      hld.for_each(0, v, f);
    }

    forr(v, V) {
      auto rev = [&](int l, int r) {
        seg.update(l, r+1, -1);
      };
      hld.for_each(0, v, rev);
    }
    cout << ans << endl;
  }
}

signed main() { cin.tie(nullptr); ios::sync_with_stdio(false); Main(); return 0; }

Submission Info

Submission Time
Task F - 根付き木のみさわさん
User shiratty8
Language C++14 (GCC 5.4.1)
Score 130
Code Size 8367 Byte
Status AC
Exec Time 828 ms
Memory 14720 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 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask_01_01.txt AC 1 ms 256 KB
subtask_01_02.txt AC 1 ms 256 KB
subtask_01_03.txt AC 1 ms 256 KB
subtask_01_04.txt AC 5 ms 256 KB
subtask_01_05.txt AC 66 ms 256 KB
subtask_01_06.txt AC 1 ms 256 KB
subtask_01_07.txt AC 4 ms 256 KB
subtask_01_08.txt AC 50 ms 256 KB
subtask_01_09.txt AC 1 ms 256 KB
subtask_01_10.txt AC 3 ms 256 KB
subtask_01_11.txt AC 48 ms 256 KB
subtask_01_12.txt AC 1 ms 256 KB
subtask_01_13.txt AC 3 ms 256 KB
subtask_01_14.txt AC 46 ms 256 KB
subtask_01_15.txt AC 1 ms 256 KB
subtask_01_16.txt AC 5 ms 256 KB
subtask_01_17.txt AC 54 ms 256 KB
subtask_01_18.txt AC 1 ms 256 KB
subtask_01_19.txt AC 3 ms 256 KB
subtask_01_20.txt AC 46 ms 256 KB
subtask_01_21.txt AC 1 ms 256 KB
subtask_01_22.txt AC 4 ms 256 KB
subtask_01_23.txt AC 53 ms 256 KB
subtask_01_24.txt AC 1 ms 256 KB
subtask_01_25.txt AC 3 ms 256 KB
subtask_01_26.txt AC 50 ms 256 KB
subtask_02_01.txt AC 700 ms 10624 KB
subtask_02_02.txt AC 712 ms 10240 KB
subtask_02_03.txt AC 767 ms 10240 KB
subtask_02_04.txt AC 439 ms 11268 KB
subtask_02_05.txt AC 449 ms 10884 KB
subtask_02_06.txt AC 475 ms 10884 KB
subtask_02_07.txt AC 297 ms 12544 KB
subtask_02_08.txt AC 364 ms 12288 KB
subtask_02_09.txt AC 389 ms 12160 KB
subtask_02_10.txt AC 220 ms 10880 KB
subtask_02_11.txt AC 232 ms 10624 KB
subtask_02_12.txt AC 283 ms 10624 KB
subtask_02_13.txt AC 467 ms 10752 KB
subtask_02_14.txt AC 477 ms 10496 KB
subtask_02_15.txt AC 501 ms 10368 KB
subtask_02_16.txt AC 439 ms 14464 KB
subtask_02_17.txt AC 423 ms 14208 KB
subtask_02_18.txt AC 461 ms 14208 KB
subtask_02_19.txt AC 503 ms 10752 KB
subtask_02_20.txt AC 516 ms 10368 KB
subtask_02_21.txt AC 561 ms 10368 KB
subtask_02_22.txt AC 449 ms 13056 KB
subtask_02_23.txt AC 424 ms 14208 KB
subtask_02_24.txt AC 435 ms 12288 KB
subtask_02_25.txt AC 828 ms 10624 KB
subtask_02_26.txt AC 695 ms 14720 KB