結果
問題 | No.1215 都市消滅ビーム |
ユーザー | chocorusk |
提出日時 | 2020-09-07 11:53:58 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,565 bytes |
コンパイル時間 | 1,863 ms |
コンパイル使用メモリ | 149,256 KB |
実行使用メモリ | 74,340 KB |
最終ジャッジ日時 | 2023-08-19 16:32:35 |
合計ジャッジ時間 | 25,411 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,592 KB |
testcase_01 | AC | 2 ms
5,388 KB |
testcase_02 | AC | 2 ms
5,360 KB |
testcase_03 | WA | - |
testcase_04 | AC | 2 ms
5,364 KB |
testcase_05 | WA | - |
testcase_06 | AC | 2 ms
5,408 KB |
testcase_07 | AC | 2 ms
5,700 KB |
testcase_08 | AC | 2 ms
5,544 KB |
testcase_09 | AC | 2 ms
5,392 KB |
testcase_10 | AC | 2 ms
5,412 KB |
testcase_11 | WA | - |
testcase_12 | AC | 2 ms
5,684 KB |
testcase_13 | AC | 322 ms
21,692 KB |
testcase_14 | AC | 419 ms
22,968 KB |
testcase_15 | AC | 1,104 ms
46,308 KB |
testcase_16 | AC | 256 ms
18,612 KB |
testcase_17 | AC | 453 ms
31,720 KB |
testcase_18 | AC | 449 ms
29,020 KB |
testcase_19 | AC | 36 ms
7,148 KB |
testcase_20 | AC | 826 ms
41,444 KB |
testcase_21 | AC | 15 ms
6,468 KB |
testcase_22 | AC | 649 ms
33,104 KB |
testcase_23 | AC | 591 ms
36,596 KB |
testcase_24 | AC | 537 ms
26,412 KB |
testcase_25 | AC | 318 ms
24,492 KB |
testcase_26 | AC | 616 ms
38,404 KB |
testcase_27 | AC | 738 ms
44,100 KB |
testcase_28 | AC | 415 ms
22,372 KB |
testcase_29 | AC | 392 ms
22,452 KB |
testcase_30 | AC | 229 ms
27,992 KB |
testcase_31 | AC | 145 ms
14,688 KB |
testcase_32 | WA | - |
testcase_33 | AC | 85 ms
19,340 KB |
testcase_34 | AC | 1,858 ms
73,912 KB |
testcase_35 | AC | 1,742 ms
74,012 KB |
testcase_36 | AC | 1,770 ms
74,068 KB |
testcase_37 | WA | - |
testcase_38 | AC | 1,575 ms
74,232 KB |
testcase_39 | AC | 1,751 ms
74,144 KB |
testcase_40 | AC | 3 ms
5,472 KB |
testcase_41 | AC | 2 ms
5,404 KB |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #define popcount __builtin_popcount using namespace std; typedef long long ll; typedef pair<int, int> P; struct LCA{ vector<vector<int>> g; vector<int> d; vector<vector<int>> p; int log; int n; LCA(const vector<vector<int>> &g):n(g.size()), g(g), d(g.size()){ log=0; while(1<<log<=n) log++; p.resize(log, vector<int>(n)); } void dfs(int x, int prev){ for(auto y:g[x]){ if(y==prev) continue; d[y]=d[x]+1; p[0][y]=x; dfs(y, x); } } void build(){ dfs(0, -1); for(int i=1; i<log; i++){ for(int j=0; j<n; j++){ p[i][j]=p[i-1][p[i-1][j]]; } } } int lca(int a, int b){ if(d[a]>d[b]) swap(a, b); int dd=d[b]-d[a], i=0; int a1=a, b1=b; while(dd){ if(dd&1) b1=p[i][b1]; dd>>=1; i++; } if(a1==b1) return a1; for(int j=log-1; j>=0; j--){ if(p[j][a1]!=p[j][b1]){ a1=p[j][a1], b1=p[j][b1]; } } return p[0][a1]; } int dist(int a, int b){ return d[a]+d[b]-2*d[lca(a, b)]; } }; int main() { int n, k; cin>>n>>k; int c[100010]; ll w[100010]; for(int i=0; i<k; i++){ cin>>c[i]; c[i]--; } for(int i=0; i<k; i++){ cin>>w[i]; } vector<vector<int>> g(n); for(int i=0; i<n-1; i++){ int a, b; cin>>a>>b; a--; b--; g[a].push_back(b); g[b].push_back(a); } LCA lca(g); lca.build(); int p0=lca.lca(c[0], c[k-1]); int d0=lca.d[p0]; int cl[100010], cr[100010]; cl[0]=c[0], cr[k-1]=c[k-1]; for(int i=1; i<k; i++) cl[i]=lca.lca(c[i], cl[i-1]); int dr[100010]; dr[k-1]=lca.d[c[k-1]]; for(int i=k-2; i>=0; i--){ cr[i]=lca.lca(c[i], cr[i+1]); dr[i]=lca.d[cr[i]]; } ll sl[100010], sr[100010], sr1[100010]; sl[0]=w[0]; for(int i=1; i<k; i++) sl[i]=sl[i-1]+w[i]; sr[k-1]=w[k-1], sr1[k-1]=sr[k-1]+lca.d[cr[k-1]]; for(int i=k-2; i>=0; i--){ sr[i]=sr[i+1]+w[i]; sr1[i]=sr[i]+lca.d[cr[i]]; } int sz=1; while(sz<k) sz<<=1; vector<vector<ll>> seg(2*sz), seg1(2*sz); for(int i=0; i<k; i++){ int t=i+sz; seg[t].push_back(sr[i]); seg1[t].push_back(sr1[i]); while(t>1){ t>>=1; seg[t].push_back(sr[i]); seg1[t].push_back(sr1[i]); } } for(int i=1; i<2*sz; i++){ sort(seg[i].begin(), seg[i].end()); sort(seg1[i].begin(), seg1[i].end()); } auto query=[&](int l, int r, ll x){ l+=sz, r+=sz; int ret=0; for(;l<r; l>>=1, r>>=1){ if(r&1){ r--; ret+=upper_bound(seg[r].begin(), seg[r].end(), x)-seg[r].begin(); } if(l&1){ ret+=upper_bound(seg[l].begin(), seg[l].end(), x)-seg[l].begin(); l++; } } return ret; }; auto query1=[&](int l, int r, ll x){ l+=sz, r+=sz; int ret=0; for(;l<r; l>>=1, r>>=1){ if(r&1){ r--; ret+=upper_bound(seg1[r].begin(), seg1[r].end(), x)-seg1[r].begin(); } if(l&1){ ret+=upper_bound(seg1[l].begin(), seg1[l].end(), x)-seg1[l].begin(); l++; } } return ret; }; ll l=-1.1e14, r=1.1e14; while(r-l>1){ ll m=(l+r)/2; ll cnt=1; for(int i=0; i<k-1; i++){ if(sl[i]+lca.d[cl[i]]<=m) cnt++; int d1=min(lca.d[cl[i]], d0); int t=lower_bound(dr, dr+k, d1)-dr; cnt+=query(max(t, i+2), k, m-d1-sl[i]); if(i+2<t){ cnt+=query1(i+2, t, m-sl[i]); } } for(int i=k-1; i>=1; i--) if(sr[i]+lca.d[cr[i]]<=m) cnt++; ll tot=(ll)k*(k+1)/2+1; if(cnt>=(tot+1)/2) r=m; else l=m; } cout<<r<<endl; return 0; }