#386793 (C++11) No.901 K-ary εxtrεεmε

提出ソース

結果

問題	No.901 K-ary εxtrεεmε
ユーザー	leaf_1415
提出日時	2019-10-04 22:33:36
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	265 ms / 3,000 ms
コード長	4,487 bytes
コンパイル時間	1,291 ms
コンパイル使用メモリ	98,044 KB
実行使用メモリ	46,728 KB
最終ジャッジ日時	2024-04-15 00:11:38
合計ジャッジ時間	8,911 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	160 ms 46,728 KB
testcase_01	AC	4 ms 8,588 KB
testcase_02	AC	5 ms 8,696 KB
testcase_03	AC	4 ms 8,084 KB
testcase_04	AC	5 ms 7,960 KB
testcase_05	AC	5 ms 8,132 KB
testcase_06	AC	5 ms 8,096 KB
testcase_07	AC	250 ms 36,168 KB
testcase_08	AC	253 ms 36,052 KB
testcase_09	AC	254 ms 36,152 KB
testcase_10	AC	255 ms 36,048 KB
testcase_11	AC	262 ms 36,048 KB
testcase_12	AC	257 ms 36,044 KB
testcase_13	AC	257 ms 36,044 KB
testcase_14	AC	265 ms 36,140 KB
testcase_15	AC	258 ms 36,052 KB
testcase_16	AC	262 ms 36,044 KB
testcase_17	AC	249 ms 36,132 KB
testcase_18	AC	252 ms 36,044 KB
testcase_19	AC	256 ms 36,052 KB
testcase_20	AC	260 ms 36,048 KB
testcase_21	AC	257 ms 36,156 KB
testcase_22	AC	265 ms 36,300 KB
testcase_23	AC	261 ms 36,284 KB
testcase_24	AC	263 ms 36,424 KB
testcase_25	AC	261 ms 36,288 KB
testcase_26	AC	262 ms 36,420 KB
testcase_27	AC	233 ms 36,040 KB
testcase_28	AC	233 ms 36,172 KB
testcase_29	AC	235 ms 36,040 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define llint long long
#define inf 1e18

using namespace std;

struct edge{
	llint to, cost;
	edge(){}
	edge(llint a, llint b){
		to = a, cost = b;
	}
};

typedef pair<int, int> P;

struct HLD{
	int V, logV;
	vector<P> mp;
	map<P, int> mp2;
	vector<P> parent;
	
	//subtree of v is [pre_order[v], back_order[v]]
	vector<int> pre_order;
	vector<int> back_order;
	
	int order;
	int global_id, local_id;
	vector<int> size, depth;
	vector<vector<int> > prev;
	
	HLD(){}
	
	void predfs(vector<int> G[], int v, int p, int d)
	{
		size[v] = 1, depth[v] = d, prev[v][0] = p;
		for(int i = 0; i < G[v].size(); i++){
			if(G[v][i] == p) continue;
			predfs(G, G[v][i], v, d+1);
			size[v] += size[G[v][i]];
		}
	}
	void maindfs(vector<int> G[], int v, int p)
	{
		mp[v] = make_pair(global_id, local_id);
		mp2[make_pair(global_id, local_id)] = v;
		pre_order[v] = ++order;
		
		if(G[v].size() == 1 && G[v][0] == p){
			back_order[v] = order;
			return;
		}
		
		vector<P> vec;
		for(int i = 0; i < G[v].size(); i++){
			if(G[v][i] == p) continue;
			vec.push_back(make_pair(size[G[v][i]], G[v][i]));
		}
		sort(vec.rbegin(), vec.rend());
		
		local_id++;
		if(vec.size() >= 1) maindfs(G, vec[0].second, v);
			
		for(int i = 1; i < vec.size(); i++){
			parent.push_back(mp[v]);
			global_id++, local_id = 0;
			maindfs(G, vec[i].second, v);
		}
		back_order[v] = order;
	}
	int getLCA(int u, int v){
		int x = u, y = v;
		if(depth[y] > depth[x]) swap(x, y);
		
		for(int i = logV-1; i >= 0; i--){
			if(depth[x] - (1<<i) >= depth[y]) x = prev[x][i];
		}
		if(x == y) return x;
		for(int i = logV-1; i >= 0; i--){
			if(prev[x][i] != prev[y][i]){
				x = prev[x][i];
				y = prev[y][i];
			}
		}
		x = prev[x][0];
		return x;
	}
	void pathcalc(int v, int lca, vector<pair<int, P> > &dest)
	{
		int gid = mp[v].first, lid = mp[v].second;
		int Gid = mp[lca].first, Lid = mp[lca].second;
		
		while(Gid != gid){
			dest.push_back(make_pair(gid, make_pair(0, lid)));
			int ngid = parent[gid].first, nlid = parent[gid].second;
			gid = ngid, lid = nlid;
		}
		dest.push_back(make_pair(gid, make_pair(Lid, lid)));
	}
	
	void init(vector<int> G[], int V) // The tree must be 1-indexed.
	{
		this->V = V, logV = 0;
		for(int t = V; t; t/=2) logV++;
		prev.resize(V+1);
		for(int i = 0; i <= V; i++) prev[i].resize(logV);
		
		size.resize(V+1), depth.resize(V+1);
		predfs(G, 1, 0, 0);
		
		prev[0][0] = 0;
		for(int i = 1; i < logV; i++){
			for(int j = 1; j <= V; j++){
				prev[j][i] = prev[prev[j][i-1]][i-1];
			}
		}
		
		mp.resize(V+1), mp2.clear();
		parent.clear(), parent.push_back(make_pair(-1, -1));
		pre_order.resize(V+1), back_order.resize(V+1);
		global_id = local_id = 0, order = 0;
		
		maindfs(G, 1, 0);
	}
	
	void path(int u, int v, vector<pair<int, P> > &dest)
	{
		dest.clear();
		int lca = getLCA(u, v);
		pathcalc(u, lca, dest);
		pathcalc(v, lca, dest);
		
		pair<int, P> p = make_pair(mp[lca].first, make_pair(mp[lca].second, mp[lca].second));
		for(int i = 0; i < dest.size(); i++){
			if(dest[i] == p){
				dest.erase(dest.begin()+i);
				return ;
			}
		}
	}
	
	void toOrder(vector<pair<int, P> > &src, vector<P> &dest)
	{
		dest.clear();
		for(int i = 0; i < src.size(); i++){
			int u = mp2[make_pair(src[i].first, src[i].second.first)], v = mp2[make_pair(src[i].first, src[i].second.second)];
			dest.push_back(make_pair(pre_order[u], pre_order[v]));
		}
	}
};

llint n, Q;
vector<int> G[100005];
vector<edge> g[100005];
llint dist[100005];
HLD hld;

void dfs(int v, int p, llint d)
{
	dist[v] = d;
	for(int i = 0; i < g[v].size(); i++){
		if(g[v][i].to == p) continue;
		dfs(g[v][i].to, v, d + g[v][i].cost);
	}
}

llint calc(llint s, llint t)
{
	llint lca = hld.getLCA(s, t);
	return dist[s] + dist[t] - 2 * dist[lca];
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	llint u, v, w;
	for(int i = 1; i <= n-1; i++){
		cin >> u >> v >> w;
		u++, v++;
		G[u].push_back(v);
		G[v].push_back(u);
		g[u].push_back(edge(v, w));
		g[v].push_back(edge(u, w));
	}
	hld.init(G, n);
	dfs(1, -1, 0);
	
	cin >> Q;
	for(int q = 0; q < Q; q++){
		llint k, x;
		vector<P> vec;
		cin >> k;
		for(int i = 0; i < k; i++){
			cin >> x;
			x++;
			vec.push_back(make_pair(hld.pre_order[x], x));
		}
		sort(vec.begin(), vec.end());
		
		llint ans = 0;
		for(int i = 0; i < k; i++){
			ans += calc(vec[i].second, vec[(i+1)%k].second);
		}
		cout << ans/2 << "\n";
	}
	flush(cout);
	
	
	return 0;
}

yukicoder

結果

テストケース

ソースコード