Submission #485786


Source Code Expand

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

struct HeavyLightDecomposition {
	vector<int> colors, positions;	//Vertex -> Color, Vertex -> Offset
	vector<int> lengths, parents, branches;	//Color -> Int, Color -> Color, Color -> Offset
	vector<int> parentnodes, depths;	//Vertex -> Vertex, Vertex -> Int
	//vector<FenwickTree>とかを避けて1次元にしたい時に使う
	//sortednodesの[lefts[v], rights[v])はvのsubtreeとなっている
	vector<int> sortednodes, offsets;	//Index -> Vertex, Color -> Index
	vector<int> lefts, rights;	//Vertex -> Index

	struct BuildDFSState {
		int i, len, parent;
		BuildDFSState() { }
		BuildDFSState(int i_, int l, int p): i(i_), len(l), parent(p) { }
	};

	//両方の辺があってもいいし、親から子への辺だけでもよい
	void build(const vector<vi> &g, int root) {
		int n = g.size();

		colors.assign(n, -1); positions.assign(n, -1);
		lengths.clear(); parents.clear(); branches.clear();
		parentnodes.assign(n, -1); depths.assign(n, -1);

		sortednodes.clear(); offsets.clear();
		lefts.assign(n, -1); rights.assign(n, -1);

		vector<int> subtreesizes;
		measure(g, root, subtreesizes);

		typedef BuildDFSState State;
		depths[root] = 0;
		vector<State> s;
		s.push_back(State(root, 0, -1));
		while(!s.empty()) {
			State t = s.back(); s.pop_back();
			int i = t.i, len = t.len;
			int index = sortednodes.size();
			int color = lengths.size();

			if(t.parent == -3) {
				rights[i] = index;
				continue;
			}

			if(t.parent != -2) {
				assert(parents.size() == color);
				parents.push_back(t.parent);
				branches.push_back(len);
				offsets.push_back(index);
				len = 0;
			}
			colors[i] = color;
			positions[i] = len;

			lefts[i] = index;
			sortednodes.push_back(i);

			int maxsize = -1, maxj = -1;
			each(j, g[i]) if(colors[*j] == -1) {
				if(maxsize < subtreesizes[*j]) {
					maxsize = subtreesizes[*j];
					maxj = *j;
				}
				parentnodes[*j] = i;
				depths[*j] = depths[i] + 1;
			}
			s.push_back(State(i, -1, -3));
			if(maxj == -1) {
				lengths.push_back(len + 1);
			}else {
				each(j, g[i]) if(colors[*j] == -1 && *j != maxj)
					s.push_back(State(*j, len, color));
				s.push_back(State(maxj, len + 1, -2));
			}
		}
	}
	
	void get(int v, int &c, int &p) const {
		c = colors[v]; p = positions[v];
	}
	bool go_up(int &c, int &p) const {
		p = branches[c]; c = parents[c];
		return c != -1;
	}

	inline const int *nodesBegin(int c) const { return &sortednodes[0] + offsets[c]; }
	inline const int *nodesEnd(int c) const { return &sortednodes[0] + (c+1 == offsets.size() ? sortednodes.size() : offsets[c+1]); }

private:
	void measure(const vector<vi> &g, int root, vector<int> &out_subtreesizes) const {
		out_subtreesizes.assign(g.size(), -1);
		vector<int> s;
		s.push_back(root);
		while(!s.empty()) {
			int i = s.back(); s.pop_back();
			if(out_subtreesizes[i] == -2) {
				int s = 1;
				each(j, g[i]) if(out_subtreesizes[*j] != -2)
					s += out_subtreesizes[*j];
				out_subtreesizes[i] = s;
			}else {
				s.push_back(i);
				each(j, g[i]) if(out_subtreesizes[*j] == -1)
					s.push_back(*j);
				out_subtreesizes[i] = -2;
			}
		}
	}
};

int main() {
	int N;
	while(~scanf("%d", &N)) {
		vector<vi> g(N);
		rep(i, N-1) {
			int a, b;
			scanf("%d%d", &a, &b), -- a, -- b;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		HeavyLightDecomposition hld;
		hld.build(g, 0);
		vector<vi> paths(hld.lengths.size());
		vi colors;
		vi v;
		int Q;
		scanf("%d", &Q);
		rep(ii, Q) {
			int M, K;
			scanf("%d%d", &M, &K);
			v.resize(M);
			rep(i, M)
				scanf("%d", &v[i]), -- v[i];
			rep(i, M) {
				int c, p;
				hld.get(v[i], c, p);
				do {
					if(paths[c].empty())
						colors.push_back(c);
					paths[c].push_back(p);
				}while(hld.go_up(c, p));
			}
			int ans = -1;
			each(i, colors) {
				if((int)paths[*i].size() >= K) {
					int k = (int)paths[*i].size() - K;
					nth_element(paths[*i].begin(), paths[*i].begin() + k, paths[*i].end());
					int p = paths[*i][k];
					amax(ans, hld.depths[hld.nodesBegin(*i)[0]] + p);
				}
			}
			printf("%d\n", ans);

			each(i, colors)
				paths[*i].clear();
			colors.clear();
		}
	}
	return 0;
}

Submission Info

Submission Time
Task F - 根付き木のみさわさん
User anta
Language C++ (GCC 4.9.2)
Score 130
Code Size 5478 Byte
Status AC
Exec Time 231 ms
Memory 19048 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:154:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &a, &b), -- a, -- b;
                                     ^
./Main.cpp:164:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &Q);
                  ^
./Main.cpp:167:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &M, &K);
                         ^
./Main.cpp:170:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &v[i]), -- v[i];
                                ^

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 31 ms 744 KB
sample_02.txt AC 27 ms 920 KB
sample_03.txt AC 26 ms 808 KB
subtask_01_01.txt AC 26 ms 924 KB
subtask_01_02.txt AC 25 ms 748 KB
subtask_01_03.txt AC 26 ms 920 KB
subtask_01_04.txt AC 26 ms 764 KB
subtask_01_05.txt AC 39 ms 924 KB
subtask_01_06.txt AC 26 ms 928 KB
subtask_01_07.txt AC 25 ms 812 KB
subtask_01_08.txt AC 34 ms 800 KB
subtask_01_09.txt AC 26 ms 808 KB
subtask_01_10.txt AC 27 ms 800 KB
subtask_01_11.txt AC 37 ms 804 KB
subtask_01_12.txt AC 25 ms 924 KB
subtask_01_13.txt AC 26 ms 916 KB
subtask_01_14.txt AC 38 ms 924 KB
subtask_01_15.txt AC 28 ms 924 KB
subtask_01_16.txt AC 27 ms 804 KB
subtask_01_17.txt AC 39 ms 928 KB
subtask_01_18.txt AC 27 ms 804 KB
subtask_01_19.txt AC 28 ms 928 KB
subtask_01_20.txt AC 35 ms 772 KB
subtask_01_21.txt AC 26 ms 920 KB
subtask_01_22.txt AC 27 ms 808 KB
subtask_01_23.txt AC 38 ms 920 KB
subtask_01_24.txt AC 27 ms 808 KB
subtask_01_25.txt AC 27 ms 804 KB
subtask_01_26.txt AC 38 ms 916 KB
subtask_02_01.txt AC 190 ms 16008 KB
subtask_02_02.txt AC 177 ms 13068 KB
subtask_02_03.txt AC 185 ms 12696 KB
subtask_02_04.txt AC 185 ms 19048 KB
subtask_02_05.txt AC 172 ms 15336 KB
subtask_02_06.txt AC 173 ms 15200 KB
subtask_02_07.txt AC 138 ms 10456 KB
subtask_02_08.txt AC 145 ms 10456 KB
subtask_02_09.txt AC 140 ms 10460 KB
subtask_02_10.txt AC 134 ms 10460 KB
subtask_02_11.txt AC 132 ms 9692 KB
subtask_02_12.txt AC 137 ms 9696 KB
subtask_02_13.txt AC 188 ms 15240 KB
subtask_02_14.txt AC 185 ms 13420 KB
subtask_02_15.txt AC 182 ms 12772 KB
subtask_02_16.txt AC 139 ms 11284 KB
subtask_02_17.txt AC 142 ms 11288 KB
subtask_02_18.txt AC 139 ms 11284 KB
subtask_02_19.txt AC 191 ms 15212 KB
subtask_02_20.txt AC 177 ms 12924 KB
subtask_02_21.txt AC 186 ms 12568 KB
subtask_02_22.txt AC 157 ms 10580 KB
subtask_02_23.txt AC 156 ms 11300 KB
subtask_02_24.txt AC 159 ms 10440 KB
subtask_02_25.txt AC 231 ms 12196 KB
subtask_02_26.txt AC 195 ms 11216 KB