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

	void add(int p, int v)
	{
		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]);
		seg.add(left[v], 1);
	}

	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
Task F - 根付き木のみさわさん
User semiexp
Language C++11 (GCC 4.9.2)
Score 130
Code Size 2768 Byte
Status
Exec Time 251 ms
Memory 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
Subtask1 20 / 20 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 110 / 110 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 48 ms 4260 KB
sample_02.txt 37 ms 4192 KB
sample_03.txt 34 ms 4260 KB
subtask_01_01.txt 34 ms 4200 KB
subtask_01_02.txt 33 ms 4188 KB
subtask_01_03.txt 33 ms 4196 KB
subtask_01_04.txt 33 ms 4192 KB
subtask_01_05.txt 51 ms 4192 KB
subtask_01_06.txt 33 ms 4188 KB
subtask_01_07.txt 35 ms 4200 KB
subtask_01_08.txt 49 ms 4200 KB
subtask_01_09.txt 33 ms 4208 KB
subtask_01_10.txt 33 ms 4204 KB
subtask_01_11.txt 49 ms 4188 KB
subtask_01_12.txt 33 ms 4188 KB
subtask_01_13.txt 34 ms 4200 KB
subtask_01_14.txt 48 ms 4188 KB
subtask_01_15.txt 33 ms 4188 KB
subtask_01_16.txt 32 ms 4192 KB
subtask_01_17.txt 51 ms 4176 KB
subtask_01_18.txt 32 ms 4188 KB
subtask_01_19.txt 33 ms 4196 KB
subtask_01_20.txt 50 ms 4256 KB
subtask_01_21.txt 32 ms 4196 KB
subtask_01_22.txt 34 ms 4192 KB
subtask_01_23.txt 51 ms 4192 KB
subtask_01_24.txt 32 ms 4188 KB
subtask_01_25.txt 32 ms 4192 KB
subtask_01_26.txt 48 ms 4244 KB
subtask_02_01.txt 168 ms 16600 KB
subtask_02_02.txt 185 ms 16136 KB
subtask_02_03.txt 192 ms 16104 KB
subtask_02_04.txt 170 ms 17124 KB
subtask_02_05.txt 176 ms 16580 KB
subtask_02_06.txt 176 ms 16608 KB
subtask_02_07.txt 198 ms 19680 KB
subtask_02_08.txt 205 ms 19436 KB
subtask_02_09.txt 215 ms 19164 KB
subtask_02_10.txt 187 ms 17244 KB
subtask_02_11.txt 195 ms 16736 KB
subtask_02_12.txt 205 ms 16612 KB
subtask_02_13.txt 186 ms 16736 KB
subtask_02_14.txt 196 ms 16480 KB
subtask_02_15.txt 198 ms 16220 KB
subtask_02_16.txt 208 ms 22872 KB
subtask_02_17.txt 210 ms 22376 KB
subtask_02_18.txt 240 ms 22240 KB
subtask_02_19.txt 192 ms 16736 KB
subtask_02_20.txt 202 ms 16224 KB
subtask_02_21.txt 212 ms 16100 KB
subtask_02_22.txt 227 ms 20572 KB
subtask_02_23.txt 251 ms 22368 KB
subtask_02_24.txt 249 ms 19160 KB
subtask_02_25.txt 206 ms 16092 KB
subtask_02_26.txt 235 ms 22120 KB