Contest Duration: ~ (local time) (180 minutes)

Submission #485749

Source Code Expand

Copy
```#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>

using namespace std;

#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

struct segtree
{
static const int DEPTH = 17;
static const int N = 1 << DEPTH;

int val[2 * N];

void init()
{
for (int i = 0; i < 2 * N; ++i) val[i] = 0;
}

{
p += N;
while (p) {
val[p] += v;
p >>= 1;
}
}

int query(int L, int R)
{
L += N;
R += N;

int ret = 0;
while (L < R) {
if (L & 1) ret += val[L++];
if (R & 1) ret += val[--R];
L >>= 1; R >>= 1;
}

return ret;
}
};

int N;
vector<int> graph[101010];
int left[101010], right[101010], id;
int depth[101010], left2pt[101010];
int pars[101010][18];

int M, K;
segtree seg;

void visit(int p, int d = 0, int rt = -1)
{
left[p] = id++;
depth[p] = d;
left2pt[left[p]] = p;

if (rt == -1) {
for (int i = 0; i < 18; ++i) pars[p][i] = -1;
} else {
pars[p][0] = rt;
for (int i = 1; i < 18; ++i) {
if (pars[p][i - 1] == -1) pars[p][i] = -1;
else pars[p][i] = pars[pars[p][i - 1]][i - 1];
}
}

for (int a : graph[p]) {
if (a != rt) {
visit(a, d + 1, p);
}
}
right[p] = id;
}

int lca(int p, int q)
{
// p, q : ordinary vertex id

if (depth[p] > depth[q]) swap(p, q);

for (int i = 17; i >= 0; --i) {
if (depth[p] <= depth[q] - (1 << i)) {
q = pars[q][i];
}
}

if (p == q) return p;

for (int i = 17; i >= 0; --i) {
if (pars[p][i] != pars[q][i]) {
p = pars[p][i];
q = pars[q][i];
}
}

return pars[p][0];
}

int valid(int p)
{
// p: ordinary vertex id

if (seg.query(left[p], right[p]) >= K) {
return depth[p];
}
return -1;
}

void solve()
{
scanf("%d%d", &M, &K);

vector<int> pts;

for (int i = 0; i < M; ++i) {
int v;
scanf("%d", &v);
--v;

pts.push_back(left[v]);
}

sort(pts.begin(), pts.end());

int ret = 0;
for (int p : pts) ret = max(ret, valid(left2pt[p]));
for (int i = 1; i < pts.size(); ++i) {
int l = lca(left2pt[pts[i - 1]], left2pt[pts[i]]);
ret = max(ret, valid(l));
}

printf("%d\n", ret);

for (int i : pts) seg.add(i, -1);
}

int main()
{
scanf("%d", &N);
for (int i = 0; i < N - 1; ++i) {
int a, b;
scanf("%d%d", &a, &b);
--a; --b;
graph[a].push_back(b);
graph[b].push_back(a);
}

id = 0;
visit(0);

seg.init();
int Q;

scanf("%d", &Q);
for (; Q--;) {
solve();
}

return 0;
}
```

#### Submission Info

Submission Time 2015-09-05 14:18:01+0900 F - 根付き木のみさわさん semiexp C++11 (GCC 4.9.2) 130 2768 Byte AC 251 ms 22872 KB

#### Compile Error

```./Main.cpp: In function ‘void solve()’:
./Main.cpp:125:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &M, &K);
^
./Main.cpp:131:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &v);
^
./Main.cpp: In function ‘int main()’:
./Main.cpp:154:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
./Main.cpp:157:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
^
./Main.cpp:169:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("...```

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
sample_01.txt 48 ms 4260 KB
sample_02.txt 37 ms 4192 KB
sample_03.txt 34 ms 4260 KB