Submission #584342
Source Code Expand
#define _CRT_SECURE_NO_WARNINGS
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #define int ll
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#define all(c) begin(c), end(c)
#define range(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) range(i,0,b)
#define rangei(i,a,b) for(ll a=a;i<=ll(b);i++)
#define repi(i,b) rangei(i,1,b)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
template<class T> ostream & operator << (ostream &os, vector<T> const &);
template<int n, class...T>
typename enable_if<(n>=sizeof...(T))>::type
_ot(ostream &, tuple<T...> const &){}
template<int n, class...T>
typename enable_if<(n< sizeof...(T))>::type
_ot(ostream &os, tuple<T...> const &t){
os << (n==0?"":" ") << get<n>(t); _ot<n+1>(os, t);
}
template<class...T>
ostream & operator << (ostream &os, tuple<T...> const &t){
_ot<0>(os, t); return os;
}
template<class T, class U>
ostream & operator<<(ostream &os, pair<T,U> const &p){
return os << "(" << p.first << ", " << p.second << ") ";
}
template<class T>
ostream & operator<<(ostream &os, vector<T> const &v){
rep(i,v.size()) os << v[i] << (i+1==(int)v.size()?"":" "); return os;
}
#ifdef DEBUG
#define dump(...) (cerr << #__VA_ARGS__ << " = " << mt(__VA_ARGS__) \
<< " [" << __LINE__ << "]" << endl)
#else
#define dump(...)
#endif
void fastios(){
ios_base::sync_with_stdio(0);
cin.tie(0);
#define endl '\n'
}
template<class T>
size_t uniq(vector<T> &v){
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
return v.size();
}
template<class T>
size_t uniq(T *l, size_t n){
sort(l,l+n);
return unique(l,l+n) - l;
}
#define mems(arr,val) memset(arr,val,sizeof(arr));
int const mod = 1000000007;
int const inf = numeric_limits<int>::max()/8;
typedef int Weight;
struct Edge {
int src, dst;
Edge(int src_, int dst_) :
src(src_), dst(dst_) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
struct HLDecomp {
const Graph &g;
int n;
vector<vector<int>> chains;
vector<int> parent, size, depth, head, last, next, prev, chain, at;
HLDecomp(const Graph &g_)
: g(g_), n(g.size()), chains(0),
parent(n, 0), size(n, 0), depth(n, -1), head(n, 0),
last(n, 0), next(n, -1), prev(n, -1), chain(n, -1), at(n, 0){
decompose();
}
int goUp(int v) const { return parent[head[v]]; }
pair<int, int> getIndex(int v) const { return make_pair(chain[v], at[v]); }
void decompose(const int root = 0){
static int stk[600010], k = 0;
stk[k++] = root; parent[root] = -1; depth[root] = 0;
while(k){
int v = stk[--k];
if(v >= 0){
stk[k++] = ~v;
for(auto &e : g[v]){
int ch = e.dst;
if(depth[ch] == -1){
depth[ch] = depth[v] + 1;
parent[ch] = v;
stk[k++] = ch;
}
}
} else {
int m = 0; v = ~v; size[v] = 1;
for(auto &e : g[v]){
int ch = e.dst;
if(parent[v] == ch) continue;
size[v] += size[ch];
if(m < size[ch]){ m = size[ch]; next[v] = ch; }
}
}
}
k = 0;
stk[k++] = root;
while(k){
int h = stk[--k];
for(auto &e : g[h]) if(parent[h] != e.dst) stk[k++] = e.dst;
if(chain[h] != -1) continue;
chains.push_back(vector<int>());
vector<int> & path = chains.back();
int cur = h;
while(cur != -1){ path.push_back(cur); cur = next[cur]; }
for(int i = 0; i < (int)path.size(); i++){
int v = path[i];
head[v] = path.front(); last[v] = path.back();
next[v] = i+1 != (int)path.size() ? path[i+1] : -1;
prev[v] = i != 0 ? path[i-1] : -1; chain[v] = chains.size() - 1; at[v] = i;
}
}
}
int lca(int u, int v){
while(chain[u] != chain[v]){
if(depth[head[u]] > depth[head[v]]) u = goUp(u);
else v = goUp(v);
}
return depth[u] < depth[v] ? u : v;
}
int solve(vector<int> const & vs, int k) const {
map<int,vector<int>> pathes;
for(int v : vs){
while(v != -1){
pathes[chain[v]].push_back(at[v]);
v = goUp(v);
}
}
int ans = -1;
for(auto & c_path : pathes){
int c = c_path.first;
auto & path = c_path.second;
if((int)path.size() >= k){
sort(path.rbegin(), path.rend());
int v = chains[c][path[k-1]];
ans = max(ans, depth[v]);
}
}
return ans;
}
};
signed main(){
fastios();
int N;
while(cin >> N){
Graph g(N);
rep(i,N-1){
int x,y;
cin >> x >> y;
x--; y--;
g[x].eb(x,y);
g[y].eb(y,x);
}
HLDecomp hld(g);
hld.decompose();
int Q;
cin >> Q;
rep(qq,Q){
int M,K;
cin >> M >> K;
vector<int> ms(M);
rep(i,M) cin >> ms[i], ms[i]--;
cout << hld.solve(ms,K) << '\n';
}
}
}
Submission Info
Submission Time |
|
Task |
F - 根付き木のみさわさん |
User |
tubo28 |
Language |
C++11 (GCC 4.9.2) |
Score |
130 |
Code Size |
5789 Byte |
Status |
AC |
Exec Time |
397 ms |
Memory |
28500 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 |
30 ms |
928 KB |
sample_02.txt |
AC |
26 ms |
924 KB |
sample_03.txt |
AC |
27 ms |
920 KB |
subtask_01_01.txt |
AC |
27 ms |
924 KB |
subtask_01_02.txt |
AC |
27 ms |
800 KB |
subtask_01_03.txt |
AC |
29 ms |
928 KB |
subtask_01_04.txt |
AC |
30 ms |
924 KB |
subtask_01_05.txt |
AC |
54 ms |
928 KB |
subtask_01_06.txt |
AC |
27 ms |
736 KB |
subtask_01_07.txt |
AC |
29 ms |
804 KB |
subtask_01_08.txt |
AC |
50 ms |
800 KB |
subtask_01_09.txt |
AC |
29 ms |
800 KB |
subtask_01_10.txt |
AC |
30 ms |
800 KB |
subtask_01_11.txt |
AC |
41 ms |
728 KB |
subtask_01_12.txt |
AC |
28 ms |
920 KB |
subtask_01_13.txt |
AC |
29 ms |
800 KB |
subtask_01_14.txt |
AC |
46 ms |
920 KB |
subtask_01_15.txt |
AC |
27 ms |
796 KB |
subtask_01_16.txt |
AC |
30 ms |
920 KB |
subtask_01_17.txt |
AC |
50 ms |
808 KB |
subtask_01_18.txt |
AC |
27 ms |
800 KB |
subtask_01_19.txt |
AC |
29 ms |
916 KB |
subtask_01_20.txt |
AC |
42 ms |
924 KB |
subtask_01_21.txt |
AC |
29 ms |
728 KB |
subtask_01_22.txt |
AC |
28 ms |
924 KB |
subtask_01_23.txt |
AC |
48 ms |
924 KB |
subtask_01_24.txt |
AC |
28 ms |
840 KB |
subtask_01_25.txt |
AC |
27 ms |
928 KB |
subtask_01_26.txt |
AC |
38 ms |
800 KB |
subtask_02_01.txt |
AC |
391 ms |
22048 KB |
subtask_02_02.txt |
AC |
389 ms |
16532 KB |
subtask_02_03.txt |
AC |
373 ms |
15508 KB |
subtask_02_04.txt |
AC |
397 ms |
28500 KB |
subtask_02_05.txt |
AC |
314 ms |
18388 KB |
subtask_02_06.txt |
AC |
313 ms |
17484 KB |
subtask_02_07.txt |
AC |
146 ms |
11472 KB |
subtask_02_08.txt |
AC |
142 ms |
11016 KB |
subtask_02_09.txt |
AC |
144 ms |
10528 KB |
subtask_02_10.txt |
AC |
144 ms |
11684 KB |
subtask_02_11.txt |
AC |
139 ms |
10536 KB |
subtask_02_12.txt |
AC |
149 ms |
10404 KB |
subtask_02_13.txt |
AC |
330 ms |
21080 KB |
subtask_02_14.txt |
AC |
312 ms |
17488 KB |
subtask_02_15.txt |
AC |
315 ms |
15688 KB |
subtask_02_16.txt |
AC |
146 ms |
11684 KB |
subtask_02_17.txt |
AC |
145 ms |
10916 KB |
subtask_02_18.txt |
AC |
159 ms |
10788 KB |
subtask_02_19.txt |
AC |
348 ms |
20944 KB |
subtask_02_20.txt |
AC |
326 ms |
16316 KB |
subtask_02_21.txt |
AC |
311 ms |
14416 KB |
subtask_02_22.txt |
AC |
169 ms |
11556 KB |
subtask_02_23.txt |
AC |
178 ms |
11096 KB |
subtask_02_24.txt |
AC |
196 ms |
10612 KB |
subtask_02_25.txt |
AC |
345 ms |
13140 KB |
subtask_02_26.txt |
AC |
213 ms |
10772 KB |