Submission #3607931


Source Code Expand

#include<map>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<string>
#include<chrono>
#include<stack>
#include<fstream>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll> 
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end()) 
#define UNIQUE_ARRAY(a,n) n = unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>=x;i--)
typedef long long ll;
using namespace std;

/*
struct point
{
long long dist; long long name;
bool operator<(const point& rhs) const {
return dist > rhs.dist;
}
};
*/
ll const MAX = 500005;
vll edge[MAX];
ll parent[MAX];
ll n;
ll tour[MAX];
ll root;
ll color[MAX] = {};
ll rk[MAX];
ll tour_ord[MAX];

bool ord(ll x, ll y) {
	return tour_ord[x] < tour_ord[y];
}

void dfs() {
	stack<ll> st;
	st.push(1);
	rk[root] = 0;
	parent[1] = 1;
	ll cnt = 1;
	while (!st.empty()) {
		ll cur = st.top();
		if (color[cur] == 0) {
			color[cur] = 1;
			tour[cnt] = cur;
			cnt++;
			REP(i, 0, SIZE(edge[cur]) - 1) {
				ll next = edge[cur][i];
				if (color[next] == 0) {
					st.push(next);
					rk[next] = rk[cur] + 1;
					parent[next] = cur;
				}
			}
		}
		else {
			st.pop();
			color[cur] = 2;
		}
	}
	REP(i, 1, n) {
		tour_ord[tour[i]] = i;
	}
}

ll parents[MAX][105];

void init() {
	REP(i, 1, n) {
		parents[i][0] = parent[i];
	}
	REP(i, 1, 50) {
		REP(j, 1, n) {
			parents[j][i] = parents[parents[j][i - 1]][i - 1];
		}
	}
}

ll getanc(ll x, ll t) {
	ll bit = 0;
	while (t > 0) {
		if ((t&BIT(bit))>0) {
			t ^= BIT(bit);
			x = parents[x][bit];
		}
		bit++;
	}
	return x;
}

ll lca(ll x, ll y) {
	if (x == y) return x;
	if (rk[x] < rk[y]) swap(x, y);
	ll t = rk[x] - rk[y];
	x = getanc(x, t);

	if (x == y) return x;
	ll bit = 0;
	
	while (BIT(bit) <= rk[x]) {
		bit++;
	}
	while (bit >= 0) {
		if (parents[x][bit] != parents[y][bit]) {
			x = parents[x][bit]; y = parents[y][bit];
		}
		bit--;
	}
	return parent[x];
}

int main() {
	cin >> n;
	REP(i, 1, n - 1) {
		ll a, b;
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	root = 1;
	dfs();
	init();
	//REP(i, 1, n) cout << tour[i] << " ";
	//cout << endl;
	ll qqq; cin >> qqq;
	REP(iii, 1, qqq) {
		ll m, k;
		cin >> m >> k;
		ll ans = -1e9;
		vll v;
		REP(i, 1, m) {
			ll t; cin >> t;
			v.push_back(t);
		}
		sort(v.begin(), v.end(), ord);
		for (ll i = 0; i + k - 1 < v.size(); i++) {
			ll j = i + k - 1;
			//cout << i << " " << j << endl;
			//cout << v[i] << " " << v[j] << " " << endl;

			ll u = lca(v[i], v[j]);
			//cout << "!" << u << endl;
			ans = max(ans, rk[u]);
		}
		cout << ans << endl;
	}
}

Submission Info

Submission Time
Task F - 根付き木のみさわさん
User nejineji
Language C++14 (GCC 5.4.1)
Score 130
Code Size 2966 Byte
Status AC
Exec Time 398 ms
Memory 115452 KB

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 8 ms 23936 KB
sample_02.txt AC 7 ms 23936 KB
sample_03.txt AC 7 ms 23936 KB
subtask_01_01.txt AC 7 ms 23936 KB
subtask_01_02.txt AC 7 ms 23936 KB
subtask_01_03.txt AC 7 ms 23936 KB
subtask_01_04.txt AC 8 ms 23936 KB
subtask_01_05.txt AC 37 ms 23936 KB
subtask_01_06.txt AC 7 ms 23936 KB
subtask_01_07.txt AC 9 ms 23936 KB
subtask_01_08.txt AC 35 ms 23936 KB
subtask_01_09.txt AC 8 ms 23936 KB
subtask_01_10.txt AC 8 ms 23936 KB
subtask_01_11.txt AC 35 ms 23936 KB
subtask_01_12.txt AC 8 ms 23936 KB
subtask_01_13.txt AC 8 ms 23936 KB
subtask_01_14.txt AC 35 ms 23936 KB
subtask_01_15.txt AC 8 ms 23936 KB
subtask_01_16.txt AC 9 ms 23936 KB
subtask_01_17.txt AC 36 ms 23936 KB
subtask_01_18.txt AC 8 ms 23936 KB
subtask_01_19.txt AC 8 ms 23936 KB
subtask_01_20.txt AC 35 ms 23936 KB
subtask_01_21.txt AC 8 ms 23936 KB
subtask_01_22.txt AC 8 ms 23936 KB
subtask_01_23.txt AC 37 ms 23936 KB
subtask_01_24.txt AC 8 ms 23936 KB
subtask_01_25.txt AC 8 ms 23936 KB
subtask_01_26.txt AC 36 ms 23936 KB
subtask_02_01.txt AC 196 ms 115320 KB
subtask_02_02.txt AC 198 ms 114560 KB
subtask_02_03.txt AC 220 ms 114432 KB
subtask_02_04.txt AC 198 ms 115452 KB
subtask_02_05.txt AC 192 ms 114488 KB
subtask_02_06.txt AC 212 ms 114432 KB
subtask_02_07.txt AC 213 ms 114092 KB
subtask_02_08.txt AC 211 ms 113612 KB
subtask_02_09.txt AC 232 ms 113256 KB
subtask_02_10.txt AC 192 ms 114168 KB
subtask_02_11.txt AC 208 ms 113212 KB
subtask_02_12.txt AC 232 ms 113280 KB
subtask_02_13.txt AC 202 ms 114812 KB
subtask_02_14.txt AC 198 ms 114300 KB
subtask_02_15.txt AC 218 ms 113984 KB
subtask_02_16.txt AC 210 ms 114116 KB
subtask_02_17.txt AC 211 ms 113396 KB
subtask_02_18.txt AC 223 ms 113228 KB
subtask_02_19.txt AC 198 ms 114812 KB
subtask_02_20.txt AC 205 ms 114008 KB
subtask_02_21.txt AC 224 ms 113792 KB
subtask_02_22.txt AC 217 ms 114152 KB
subtask_02_23.txt AC 210 ms 113684 KB
subtask_02_24.txt AC 232 ms 113204 KB
subtask_02_25.txt AC 398 ms 113920 KB
subtask_02_26.txt AC 386 ms 113740 KB