QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#360755#6350. MITppipTL 18ms38456kbC++143.1kb2024-03-22 07:37:402024-03-22 07:37:41

Judging History

你现在查看的是最新测评结果

  • [2024-03-22 07:37:41]
  • 评测
  • 测评结果:TL
  • 用时:18ms
  • 内存:38456kb
  • [2024-03-22 07:37:40]
  • 提交

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...

result: