QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#360755 | #6350. MIT | ppip | TL | 18ms | 38456kb | C++14 | 3.1kb | 2024-03-22 07:37:40 | 2024-03-22 07:37:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using LL=long long;
constexpr int N(1e6);
int n;
int fa[N+5],dep[N+5],DEP[N+5],FA[N+5];
int L[N+5],R[N+5],fz[N+5];
vector<pair<int,int>> e[N+5];
int lb[N+5];
LL d[N+5];
void init(int u,int fa) {
::fa[u]=fa;
dep[u]=dep[fa]+1;
static int lda{0};
L[u]=++lda;
fz[lda]=u;
int p{fa},q{lb[fa]},r{lb[q]};
lb[u]=(dep[lb[p]]-dep[lb[q]]!=dep[lb[q]]-dep[lb[r]]?p:r);
for (auto [v,w]:e[u])
if (v!=fa) {
d[v]=d[u]+w;
init(v,u);
}
R[u]=lda;
}
inline int LCA(int u, int v) {
if (dep[u]<dep[v]) swap(u, v);
while (dep[u]>dep[v])
if (dep[lb[u]]<dep[v])
u=fa[u];
else
u=lb[u];
while (u!=v)
if (lb[u]==lb[v])
u=fa[u],v=fa[v];
else
u=lb[u],v=lb[v];
return u;
}
inline LL dis(int u,int v) { return d[u]+d[v]-2*d[LCA(u,v)]; }
int jmp(int u,int k) {
k=dep[u]-k;
while (dep[u]>k) {
if (dep[lb[u]]<k) u=fa[u];
else u=lb[u];
}
return u;
}
bool son(int u,int v) { return L[u]<=L[v]&&L[v]<=R[u]; }
int jump(int a,int b) { return son(a,b)?jmp(b,dep[b]-dep[a]-1):fa[a]; }
// tree basic op end
struct fenwick {
int t[N+5];
void add(int x) {
for (;x<=n;x+=x&-x) ++t[x];
}
int qry(int u) {
int l{L[u]-1},r{R[u]},ans{0};
while (r>l) ans+=t[r],r&=r-1;
while (l>r) ans-=t[l],l&=l-1;
return ans;
}
} T;
struct centroid {
int cnt;
set<int> dots;
int getwt(int v) { return son(cnt,v)?T.qry(jump(cnt,v)):dots.size()-T.qry(cnt); }
int nxt(int p) {
auto it{dots.lower_bound(p)};
if (it==dots.end()) return n+1;
return *it;
}
int pre(int p) {
auto it{dots.upper_bound(p)};
if (it==dots.begin()) return 0;
return *prev(it);
}
int move(int v) {
if (son(cnt,v)) {
int a{jump(cnt,v)};
return LCA(fz[nxt(L[a])],fz[pre(R[a])]);
}
int l{L[cnt]},r{R[cnt]};
int x{v};
for (auto y:{nxt(1),pre(l-1),nxt(r+1),pre(n)}) {
if (y==0||y==n+1||l<=y&&y<=r) continue;
x=LCA(x,fz[y])^LCA(x,cnt)^LCA(fz[y],cnt);
}
return x;
}
void add(int v) {
dots.insert(L[v]);
T.add(L[v]);
if (v==cnt) return;
int wt{getwt(v)};
if (2*wt<=dots.size()) return;
int to{move(v)};
cnt=to;
}
} C;
using P=array<int,2>;
P operator+(const P &a,const P &b) {
if (a[0]==-1) return b;
if (b[0]==-1) return a;
auto [x,y]=a;
LL xy{dis(x,y)};
for (auto z:b) {
LL xz{dis(x,z)},yz{dis(y,z)},mx{max({xy,xz,yz})};
if (mx==xz) y=z,xy=xz;
else if (mx==yz) x=z,xy=yz;
}
return {x,y};
}
struct segtree {
P t[N<<1];
void build() {
for (int i{1};i<=n;++i) t[i+n-1]={i,i};
for (int i{n-1};i>=1;--i)
t[i]=t[i<<1]+t[i<<1|1];
}
void mod(int x) {
t[x+=n-1]={-1,-1};
while (x>>=1) t[x]=t[x<<1]+t[x<<1|1];
}
} S;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n;
for (int i{1};i<n;++i) {
int u,v,w;cin>>u>>v>>w;
e[u].emplace_back(v,w);
e[v].emplace_back(u,w);
}
init(1,0);
C.cnt=1;S.build();
LL ans{0};
for (int i{1};i<=n;++i) {
int cnt{C.cnt};
auto [a,b]{S.t[1]};
LL xa{dis(a,cnt)},xb{dis(b,cnt)};
if (xa<xb) a=b,xa=xb;
S.mod(a);C.add(a);
ans+=xa-dis(cnt,C.cnt);
if (~i&1) cout<<ans<<" ";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 38456kb
input:
7 1 3 99 2 3 82 3 4 4 4 5 43 5 6 5 4 7 3
output:
181 280 287
result:
ok 3 number(s): "181 280 287"
Test #2:
score: 0
Accepted
time: 18ms
memory: 36604kb
input:
1000 328 12 58771429 881 504 17030494 847 622 20805817 12 922 58532669 879 929 52585738 495 726 27873950 855 17 37971674 797 941 76999719 702 610 719916 479 127 97829887 731 557 55300256 282 615 88802280 651 318 64099880 540 51 6547869 896 54 87823596 674 879 80674008 77 691 54802376 193 851 7869172...
output:
48829042195 97562386542 146216474947 194713456438 243120633399 291394542517 339657517459 387785045812 435787622310 483691355869 531476208289 579153483709 626793764008 674259794140 721617453738 768862531418 816032104456 863044440224 909960999950 956790589086 1003491332151 1050093110804 1096582356539 ...
result:
ok 500 numbers
Test #3:
score: 0
Accepted
time: 10ms
memory: 36596kb
input:
1000 739 878 29520635 133 940 5021186 160 908 26446479 441 122 80604853 539 396 95959331 635 860 46393560 387 172 58313059 53 442 65841670 121 159 59547874 35 264 28494605 269 78 29571243 436 384 89754669 619 47 52195144 57 336 95094232 936 419 88183176 877 634 14912042 47 100 57449297 533 101 61185...
output:
1335958866 2626054407 3904456915 5174845834 6437211717 7689455676 8928545787 10163335876 11395869036 12622043944 13839303826 15049898576 16256276325 17459646468 18659090162 19856778178 21048658276 22239285858 23421421030 24597109238 25772007715 26944410577 28111355238 29275440829 30439025973 3160110...
result:
ok 500 numbers
Test #4:
score: -100
Time Limit Exceeded
input:
10000 8832 9937 83287693 1229 3010 26805846 5184 8703 32371496 5692 201 90600077 7857 7922 2427036 6991 1815 55936149 9126 8434 96181780 2395 5238 99604883 3721 3882 32707216 6961 5616 4158592 479 2786 52279400 9395 164 84498120 9470 462 16429465 8303 9717 36203661 4462 3119 77535638 9010 5633 83602...
output:
501483023048 1002862634577 1504180026111 2005449794525 2506536411562 3007537456615 3508449380203 4009328554633 4510105447462 5010869687212 5511538034705 6012089525686 6512463969594 7012812594398 7513027036015 8013205824561 8513282014876 9013342841924 9513374638228 10013328423574 10513136286282 11012...