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