結果
問題 | No.1215 都市消滅ビーム |
ユーザー | autumn-eel |
提出日時 | 2020-08-30 09:41:43 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,399 ms / 6,000 ms |
コード長 | 3,423 bytes |
コンパイル時間 | 2,667 ms |
コンパイル使用メモリ | 190,372 KB |
実行使用メモリ | 28,864 KB |
最終ジャッジ日時 | 2024-11-15 06:21:35 |
合計ジャッジ時間 | 28,448 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 3 ms
6,816 KB |
testcase_02 | AC | 3 ms
7,764 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 3 ms
7,632 KB |
testcase_05 | AC | 3 ms
7,636 KB |
testcase_06 | AC | 3 ms
7,632 KB |
testcase_07 | AC | 3 ms
7,772 KB |
testcase_08 | AC | 3 ms
7,892 KB |
testcase_09 | AC | 2 ms
6,820 KB |
testcase_10 | AC | 3 ms
7,636 KB |
testcase_11 | AC | 3 ms
6,820 KB |
testcase_12 | AC | 2 ms
6,816 KB |
testcase_13 | AC | 442 ms
12,244 KB |
testcase_14 | AC | 560 ms
13,456 KB |
testcase_15 | AC | 1,364 ms
19,612 KB |
testcase_16 | AC | 393 ms
10,400 KB |
testcase_17 | AC | 555 ms
20,380 KB |
testcase_18 | AC | 607 ms
15,620 KB |
testcase_19 | AC | 56 ms
6,816 KB |
testcase_20 | AC | 1,118 ms
19,148 KB |
testcase_21 | AC | 17 ms
6,820 KB |
testcase_22 | AC | 874 ms
16,588 KB |
testcase_23 | AC | 811 ms
17,728 KB |
testcase_24 | AC | 660 ms
15,160 KB |
testcase_25 | AC | 430 ms
14,804 KB |
testcase_26 | AC | 858 ms
20,200 KB |
testcase_27 | AC | 931 ms
23,692 KB |
testcase_28 | AC | 561 ms
11,548 KB |
testcase_29 | AC | 491 ms
13,704 KB |
testcase_30 | AC | 265 ms
18,996 KB |
testcase_31 | AC | 207 ms
9,924 KB |
testcase_32 | AC | 63 ms
19,600 KB |
testcase_33 | AC | 64 ms
15,448 KB |
testcase_34 | AC | 2,374 ms
28,264 KB |
testcase_35 | AC | 2,377 ms
28,864 KB |
testcase_36 | AC | 2,356 ms
27,888 KB |
testcase_37 | AC | 1,947 ms
28,620 KB |
testcase_38 | AC | 1,272 ms
28,744 KB |
testcase_39 | AC | 2,399 ms
28,560 KB |
testcase_40 | AC | 3 ms
7,760 KB |
testcase_41 | AC | 2 ms
6,824 KB |
ソースコード
#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<int>>E; vector<vector<int>>par; vector<int>d1; int MAX_LOG=18; int n; LCA(){} LCA(int N){ n=N; E=vector<vector<int>>(n); par=vector<vector<int>>(MAX_LOG,vector<int>(n)); d1=vector<int>(n); } void add_edge(int a,int b){ E[a].push_back(b); E[b].push_back(a); } private: void dfs(int u,int p,int a){ par[0][u]=p;d1[u]=a; for(auto&v:E[u]){ if(v!=p)dfs(v,u,a+1); } } bool flag=false; void init(){ dfs(0,-1,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]; } }; template<class T> class BIT{ public: vector<T>bit; T cnt; BIT(int n){ bit=vector<T>(n+10); cnt=0; } void add(int k,T x){ k++; while(k<(int)bit.size()){ bit[k]+=x; k+=k&-k; } cnt+=x; } T sum(int k){ k++; T res=0; while(k){ res+=bit[k]; k-=k&-k; } return res; } T sum2(int k){ return cnt-sum(k); } }; LCA lca; int n,K; int c[200000]; ll d[200000]; int L[200000],R[200000];//lca from left,right int LR[200000]; // left+right end int b[200000]; ll calc1(ll t){//score only ll ans=0; BIT<int>bit(K); vector<P>query; ll S=0; rep(i,K-2){ int dep=lca.d1[LR[i]]; 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){ bit.add(sum[g].second,1); g++; } ans+=bit.sum2(p.second-1); } return ans; } struct st{ ll a,b,c; }; ll calc2(ll t){//score+depth ll ans=0; BIT<int>bit(K); 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){ bit.add(sum[g].second,1); g++; } ans+=bit.sum(p.c-1)-bit.sum(p.b-1); } return ans; } ll C(ll t){ ll cnt=0; cnt+=calc1(t); cnt+=calc2(t); 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]); LR[i]=node; 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; E=(E+1)/2-1; ll ok=2e14,ng=-2e14; while(ok-ng>1){ ll t=(ok+ng)/2; if(C(t)>=E)ok=t; else ng=t; } cout<<ok<<endl; }