Submission #2225616


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 <typename V> struct SegTreeLazy {
  static const V zero = 0;
  static const V def = 0;
  struct Node {
    V dat;
    V lazy;
    bool flag;
    Node() : dat(def), lazy(zero), flag(false) {}
  };

  static V merge(const V &l, const V &r) {
    return max(l, r);
  }

  const int N;
  vector<Node> seg;

  SegTreeLazy(int size) : N(p2(size)), seg(N * 2) {};

  void update(int a, int b, V v) {
    update(a, b, v, 0, 0, N);
  }

  V query(int a, int b) {
    return query(a, b, 0, 0, N);
  }

  private:
  void push(int k, int l, int r) {
    if (seg[k].flag) {
      seg[k].dat += seg[k].lazy;
      if (r - l > 1) {
        seg[k * 2 + 1].lazy += seg[k].lazy;
        seg[k * 2 + 2].lazy += seg[k].lazy;
        seg[k * 2 + 1].flag = true;
        seg[k * 2 + 2].flag = true;
      }
      seg[k].lazy = zero;
      seg[k].flag = false;
    }
  }

  void update(int a, int b, V v, int k, int l, int r) {
    push(k, l, r);
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
      seg[k].lazy = v;
      seg[k].flag = true;
      push(k, l, r);
    }
    else {
      update(a, b, v, k * 2 + 1, l, (l + r) / 2);
      update(a, b, v, k * 2 + 2, (l + r) / 2, r);
      seg[k].dat = merge(seg[k * 2 + 1].dat, seg[k * 2 + 2].dat);
    }
  }

  V query(int a, int b, int k, int l, int r) {
    push(k, l, r);
    if (r <= a || b <= l) return zero;
    if (a <= l && r <= b) return seg[k].dat;
    V x = query(a, b, k * 2 + 1, l, (l + r) / 2);
    V y = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return merge(x, y);
  }

  static int p2(int n, int m=1) { return m >= n ? m : p2(n, m * 2); }
};

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);
  SegTreeLazy<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 8145 Byte
Status AC
Exec Time 746 ms
Memory 15744 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 4 ms 256 KB
subtask_01_05.txt AC 64 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 49 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 51 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 53 ms 256 KB
subtask_01_18.txt AC 1 ms 256 KB
subtask_01_19.txt AC 4 ms 256 KB
subtask_01_20.txt AC 48 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 52 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 49 ms 256 KB
subtask_02_01.txt AC 596 ms 11776 KB
subtask_02_02.txt AC 593 ms 11264 KB
subtask_02_03.txt AC 637 ms 11264 KB
subtask_02_04.txt AC 365 ms 12292 KB
subtask_02_05.txt AC 371 ms 11908 KB
subtask_02_06.txt AC 402 ms 11908 KB
subtask_02_07.txt AC 269 ms 13568 KB
subtask_02_08.txt AC 329 ms 13312 KB
subtask_02_09.txt AC 373 ms 13184 KB
subtask_02_10.txt AC 206 ms 11904 KB
subtask_02_11.txt AC 218 ms 11648 KB
subtask_02_12.txt AC 274 ms 11648 KB
subtask_02_13.txt AC 399 ms 11776 KB
subtask_02_14.txt AC 403 ms 11520 KB
subtask_02_15.txt AC 439 ms 11392 KB
subtask_02_16.txt AC 374 ms 15488 KB
subtask_02_17.txt AC 380 ms 15232 KB
subtask_02_18.txt AC 457 ms 15232 KB
subtask_02_19.txt AC 424 ms 11776 KB
subtask_02_20.txt AC 443 ms 11392 KB
subtask_02_21.txt AC 489 ms 11392 KB
subtask_02_22.txt AC 388 ms 14080 KB
subtask_02_23.txt AC 379 ms 15232 KB
subtask_02_24.txt AC 411 ms 13184 KB
subtask_02_25.txt AC 746 ms 11648 KB
subtask_02_26.txt AC 725 ms 15744 KB