結果

問題 No.901 K-ary εxtrεεmε
ユーザー latte0119latte0119
提出日時 2019-10-05 01:22:04
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 416 ms / 3,000 ms
コード長 3,411 bytes
コンパイル時間 1,872 ms
コンパイル使用メモリ 182,756 KB
実行使用メモリ 36,000 KB
最終ジャッジ日時 2024-04-15 00:15:16
合計ジャッジ時間 10,231 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 295 ms
36,000 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 5 ms
6,944 KB
testcase_03 AC 5 ms
6,944 KB
testcase_04 AC 5 ms
6,940 KB
testcase_05 AC 6 ms
6,944 KB
testcase_06 AC 5 ms
6,944 KB
testcase_07 AC 252 ms
32,032 KB
testcase_08 AC 244 ms
31,900 KB
testcase_09 AC 227 ms
32,024 KB
testcase_10 AC 243 ms
32,032 KB
testcase_11 AC 256 ms
32,156 KB
testcase_12 AC 289 ms
32,156 KB
testcase_13 AC 276 ms
32,024 KB
testcase_14 AC 265 ms
32,028 KB
testcase_15 AC 274 ms
32,028 KB
testcase_16 AC 283 ms
32,028 KB
testcase_17 AC 416 ms
32,160 KB
testcase_18 AC 373 ms
32,156 KB
testcase_19 AC 416 ms
32,156 KB
testcase_20 AC 379 ms
31,904 KB
testcase_21 AC 367 ms
32,024 KB
testcase_22 AC 277 ms
32,796 KB
testcase_23 AC 267 ms
32,924 KB
testcase_24 AC 268 ms
32,924 KB
testcase_25 AC 272 ms
32,792 KB
testcase_26 AC 273 ms
32,924 KB
testcase_27 AC 125 ms
32,028 KB
testcase_28 AC 138 ms
32,004 KB
testcase_29 AC 140 ms
32,028 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:140:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  140 |         int K;scanf("%lld",&K);
      |               ~~~~~^~~~~~~~~~~
main.cpp:141:33: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  141 |         vint vs(K);rep(i,K)scanf("%lld",&vs[i]);
      |                            ~~~~~^~~~~~~~~~~~~~~
main.cpp: In function ‘int main()’:
main.cpp:174:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  174 |         int N;scanf("%lld",&N);
      |               ~~~~~^~~~~~~~~~~
main.cpp:178:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  178 |                 scanf("%lld%lld%lld",&a,&b,&c);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:184:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  184 |         int Q;scanf("%lld",&Q);
      |               ~~~~~^~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class W,int lg=1>
struct WeightedTree{
	struct Edge{
		int to;
		W cost;
		Edge(int to,W cost):to(to),cost(cost){}
	};

	int V;
	vector<vector<Edge>>G;

	vector<vector<int>>par;
	vector<int>dep,sz,head;
	vector<int>tin,tout;
	vector<W>dist;
	WeightedTree(int V=0):V(V),G(V),par(lg,vector<int>(V)),sz(V),dep(V),head(V),dist(V),tin(V),tout(V){}

	void addEdge(int a,int b,W c=W(1)){
		G[a].push_back(Edge(b,c));
		G[b].push_back(Edge(a,c));
	}

	void dfs(int v,int p,int d,W c){
		par[0][v]=p;
		dep[v]=d;
		sz[v]=1;
		dist[v]=c;

		for(auto &e:G[v]){
			if(e.to==p)continue;
			dfs(e.to,v,d+1,c+e.cost);
			sz[v]+=sz[e.to];
			if(G[v][0].to==p||sz[e.to]>sz[G[v][0].to])swap(G[v][0],e);
		}
	}

	void dfs_hld(int v,int &tt){
		tin[v]=tt++;
		for(auto &e:G[v]){
			if(e.to==par[0][v])continue;
			head[e.to]=(e.to==G[v][0].to)?head[v]:e.to;
			dfs_hld(e.to,tt);
		}
		tout[v]=tt;
	}
	void init(){
		dfs(0,-1,0,W(0));
		int tt=0;
		dfs_hld(0,tt);

		for(int i=0;i+1<lg;i++){
			for(int j=0;j<V;j++){
				if(par[i][j]==-1)par[i+1][j]=-1;
				else par[i+1][j]=par[i][par[i][j]];
			}
		}
	}

	// 1<<lg >=N-1!!!!!
	int getLCA(int u,int v){
		
		if(dep[u]<dep[v])swap(u,v);
		rep(i,lg)if((dep[u]-dep[v])>>i&1)u=par[i][u];
		if(u==v)return u;

		for(int i=lg-1;i>=0;i--)if(par[i][u]!=par[i][v])u=par[i][u],v=par[i][v];
		return par[0][v];
	}

	int getLength(int a,int b=0){
		int l=getLCA(a,b);
		return dep[a]+dep[b]-2*dep[l];
	}
	W getDistance(int a,int b=0){
		int l=getLCA(a,b);
		return dist[a]+dist[b]-2*dist[l];
	}

	int getParent(int v,int k=0){
		return par[k][v];
	}
	int getDepth(int v){
		return dep[v];
	}
	int getIn(int v){
		return tin[v];
	}
	int getOut(int v){
		return tout[v];
	}
};

/*
0-indexed
add(k,x): a[k]+=x
sum(k): sum(a[0,k])
space:O(N)
time:O(logN) per query
*/
struct BinaryIndexedTree{
	int n;
	vector<int>dat;
	BinaryIndexedTree(int n=0):n(n){
		dat.resize(n+1);
	}
	void add(int k,int x){
		for(k++;k<=n;k+=k&-k)dat[k]+=x;
	}
	int sum(int k){
		int ret=0;
		for(k++;k;k-=k&-k)ret+=dat[k];
		return ret;
	}
};



WeightedTree<int,20>T;

BinaryIndexedTree bit(111111);

void solve(){
	int K;scanf("%lld",&K);
	vint vs(K);rep(i,K)scanf("%lld",&vs[i]);

	set<pint>s;
	rep(i,K){
		s.insert({T.getDepth(vs[i]),vs[i]});
		bit.add(T.getIn(vs[i]),1);
	}
	int ans=0;
	
	
	
	while(s.size()>1){
		int v=s.rbegin()->se;
		s.erase(*s.rbegin());
		bit.add(T.getIn(v),-1);
		int u=v;
		for(int i=19;i>=0;i--){
			if(T.getParent(u,i)==-1)continue;
			int w=T.getParent(u,i);
			if(bit.sum(T.getOut(w)-1)-bit.sum(T.getIn(w)-1)==0){
				u=w;
			}
		}
		u=T.getParent(u);
		ans+=T.getDistance(u,v);
		if(s.find(pint(T.getDepth(u),u))!=s.end())continue;
		bit.add(T.getIn(u),1);
		s.insert(pint(T.getDepth(u),u));
	}
	printf("%lld\n",ans);
}

signed main(){
	int N;scanf("%lld",&N);
	T=WeightedTree<int,20>(N);
	rep(i,N-1){
		int a,b,c;
		scanf("%lld%lld%lld",&a,&b,&c);
		T.addEdge(a,b,c);
	}

	T.init();

	int Q;scanf("%lld",&Q);

	while(Q--){
		solve();
	}
	return 0;
}
0