結果

問題 No.1215 都市消滅ビーム
ユーザー autumn-eelautumn-eel
提出日時 2020-08-30 08:19:48
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 4,178 ms / 6,000 ms
コード長 4,265 bytes
コンパイル時間 2,749 ms
コンパイル使用メモリ 196,952 KB
実行使用メモリ 29,716 KB
最終ジャッジ日時 2024-11-15 06:10:57
合計ジャッジ時間 44,886 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 3 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 3 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 753 ms
11,680 KB
testcase_14 AC 892 ms
10,836 KB
testcase_15 AC 2,163 ms
20,312 KB
testcase_16 AC 656 ms
9,384 KB
testcase_17 AC 944 ms
19,452 KB
testcase_18 AC 945 ms
15,660 KB
testcase_19 AC 89 ms
5,248 KB
testcase_20 AC 1,776 ms
18,020 KB
testcase_21 AC 26 ms
5,248 KB
testcase_22 AC 1,391 ms
14,548 KB
testcase_23 AC 1,316 ms
18,260 KB
testcase_24 AC 1,094 ms
13,100 KB
testcase_25 AC 692 ms
12,460 KB
testcase_26 AC 1,353 ms
18,956 KB
testcase_27 AC 1,581 ms
23,516 KB
testcase_28 AC 972 ms
10,852 KB
testcase_29 AC 813 ms
11,216 KB
testcase_30 AC 441 ms
19,900 KB
testcase_31 AC 350 ms
8,804 KB
testcase_32 AC 68 ms
18,208 KB
testcase_33 AC 83 ms
15,424 KB
testcase_34 AC 3,853 ms
29,692 KB
testcase_35 AC 3,807 ms
29,688 KB
testcase_36 AC 4,178 ms
29,568 KB
testcase_37 AC 3,377 ms
29,584 KB
testcase_38 AC 2,765 ms
29,716 KB
testcase_39 AC 4,146 ms
29,580 KB
testcase_40 AC 2 ms
5,248 KB
testcase_41 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;

class LCA{
public:
	vector<vector<pair<int,int>>>E;
	vector<vector<int>>par;
	vector<int>d1;
	vector<long long>d2;
	int MAX_LOG=22;
	int n;
	LCA(){}
	LCA(int N){
		n=N;
		E=vector<vector<pair<int,int>>>(n);
		par=vector<vector<int>>(MAX_LOG,vector<int>(n));
		d1=vector<int>(n);
		d2=vector<long long>(n);
	}
	void add_edge(int a,int b,int c){
		E[a].push_back(make_pair(c,b));
		E[b].push_back(make_pair(c,a));
	}
	void add_edge(int a,int b){
		E[a].push_back(make_pair(1,b));
		E[b].push_back(make_pair(1,a));
	}
private:
	void dfs(int u,int p,int a,long long b){
		par[0][u]=p;d1[u]=a;d2[u]=b;
		for(auto&v:E[u]){
			if(v.second!=p)dfs(v.second,u,a+1,b+v.first);
		}
	}
	bool flag=false;
	void init(){
		dfs(0,-1,0,0);
		for(int i=1;i<MAX_LOG;i++)for(int j=0;j<n;j++){
			if(par[i-1][j]==-1)par[i][j]=-1;
			else par[i][j]=par[i-1][par[i-1][j]];
		}
		flag=true;
	}
public:
	int lca(int u,int v){
		if(!flag)init();
		if(d1[u]>d1[v])swap(u,v);
		for(int i=0;i<MAX_LOG;i++){
			if((d1[v]-d1[u])>>i&1)v=par[i][v];
		}
		if(u==v)return u;
		for(int i=MAX_LOG-1;i>=0;i--){
			if(par[i][u]!=par[i][v]){
				u=par[i][u];
				v=par[i][v];
			}
		}
		return par[0][u];
	}
	long long dist(int u,int v){
		int l=lca(u,v);
		return d2[u]+d2[v]-d2[l]*2;
	}
};

template<class T>
class Segtree{
	int n;
	vector<T>dat;
	T INIT;
	T E;
	function<T(T,T)>F;
public:
	Segtree(int n_,T INIT,T E,function<T(T,T)>F):INIT(INIT),E(E),F(F){
		n=1;while(n<n_)n<<=1;
		dat=vector<T>(2*n,INIT);
	}
	void set(int k,T x){
		k+=n;
		dat[k]=x;
		while(k>1){
			k>>=1;
			dat[k]=F(dat[k<<1],dat[(k<<1)+1]);
		}
	}
	void update(int k,T x){
		k+=n;
		dat[k]=F(dat[k],x);
		while(k>1){
			k>>=1;
			dat[k]=F(dat[k<<1],dat[(k<<1)+1]);
		}
	}
	T query(int l,int r){
		T resl=E,resr=E;
		for(l+=n,r+=n;l<r;l>>=1,r>>=1){
			if(l&1)resl=F(resl,dat[l++]);
			if(r&1)resr=F(dat[--r],resr);
		}
		return F(resl,resr);
	}
};

LCA lca;

int n,K;
int c[200000];
ll d[200000];

int L[200000],R[200000];//lca from left,right
int b[200000];

ll calc1(ll t){//score only
	ll ans=0;
	Segtree<int>seg(K,0,0,[](int a,int b){return a+b;});
	vector<P>query;
	ll S=0;
	rep(i,K-2){
		int dep=lca.d1[lca.lca(L[i],c[K-1])];
		S+=d[i];
		query.push_back(P(t-dep-S,b[i]));
	}
	S=0;
	rep(i,K-1){
		S+=d[i];
		if(S+lca.d1[L[i]]<=t)ans++;
	}
	sort(query.begin(),query.end());
	vector<P>sum;
	ll s=0;
	for(int i=K-1;i>=0;i--){
		s+=d[i];
		sum.push_back(P(s,i));
	}
	sort(sum.begin(),sum.end());
	int g=0;
	for(auto p:query){
		while(g<sum.size()&&sum[g].first<=p.first){
			seg.update(sum[g].second,1);
			g++;
		}
		ans+=seg.query(p.second,K);
	}
	return ans;
}

struct st{
	ll a,b,c;
};

ll calc2(ll t){//score+depth
	ll ans=0;
	Segtree<int>seg(K,0,0,[](int a,int b){return a+b;});
	vector<st>query;
	query.push_back({t,0,K});
	ll S=0;
	rep(i,K-2){
		S+=d[i];
		query.push_back({t-S,i+2,b[i]});
	}
	sort(query.begin(),query.end(),[](st a,st b){return a.a<b.a;});
	vector<P>sum;
	ll s=0;
	for(int i=K-1;i>=0;i--){
		s+=d[i];
		sum.push_back(P(s+lca.d1[R[i]],i));
	}
	sort(sum.begin(),sum.end());
	int g=0;
	for(auto p:query){
		while(g<sum.size()&&sum[g].first<=p.a){
			seg.update(sum[g].second,1);
			g++;
		}
		ans+=seg.query(p.b,p.c);
	}
	return ans;
}

ll C(ll t){
	ll cnt=0;
	cnt+=calc1(t);
	cnt+=calc2(t);
	//~ cout<<t<<' '<<calc1(t)<<' '<<calc2(t)<<endl;
	return cnt;
}

int main(){
	cin>>n>>K;
	lca=LCA(n);
	rep(i,K){
		scanf("%d",&c[i]);c[i]--;
	}
	rep(i,K)scanf("%lld",&d[i]);
	rep(i,n-1){
		int a,b;scanf("%d%d",&a,&b);a--;b--;
		lca.add_edge(a,b);
	}
	lca.lca(0,1);
	for(int i=K-1;i>=0;i--){
		if(i==K-1)R[i]=c[i];
		else R[i]=lca.lca(R[i+1],c[i]);
	}
	rep(i,K){
		if(i==0)L[i]=c[i];
		else L[i]=lca.lca(L[i-1],c[i]);
	}
	rep(i,K-2){
		int ok=K-1,ng=i+1;
		int node=lca.lca(c[K-1],L[i]);
		while(ok-ng>1){
			int t=(ok+ng)/2;
			if(lca.lca(L[i],R[t])==node)ok=t;
			else ng=t;
		}
		b[i]=ok;
	}
	ll E=K*(ll)(K+1)/2+1;
	//~ cout<<"E="<<E<<endl;
	E=(E+1)/2-1;
	//~ cout<<"E="<<E<<endl;
	ll ok=LLONG_MAX/3,ng=LLONG_MIN/3;
	while(ok-ng>1){
		ll t=(ok+ng)/2;
		if(C(t)>=E)ok=t;
		else ng=t;
	}
	cout<<ok<<endl;
}
/*
3 2
2 3
1 1
1 2
2 3
*/

/*
7 3
4 5 7
1 10 100
1 2
2 3
3 4
3 5
1 6
6 7
*/
0