QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#368243#6350. MITppipTL 3ms38460kbC++144.7kb2024-03-26 22:19:192024-03-26 22:19:19

Judging History

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

  • [2024-03-26 22:19:19]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:38460kb
  • [2024-03-26 22:19:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
constexpr int S1=1<<20;
char buf1[S1],*l1,*r1;
#define getchar() ((l1==r1&&(r1=(l1=buf1)+fread(buf1,1,S1,stdin)),l1!=r1)?*l1++:EOF)
template<typename T=int>inline T read()
{
	T x=0;
	char c=getchar();
	while(c<'0'||c>'9')
		c=getchar();
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
constexpr int S2=1<<20;
char buf2[S2],*l2=buf2;
#define putchar(c) (l2==buf2+S2&&(fwrite(buf2,1,S2,stdout),l2=buf2),*l2++=(c))
int _st[22];
template<typename T>inline void write(T x)
{
	int tp=0;
	do
		_st[++tp]=x%10;
	while(x/=10);
	while(tp)
		putchar(_st[tp--]+'0');
	putchar(' ');
}
constexpr int N(1e6);
using LL=long long;
pair<int,int> E[N*2];
int beg[N+5];
int fa[N+5],d[N+5],lb[N+5];
int L[N+5],R[N+5],fz[N+5],sz[N+5];
LL h[N+5];
void init(int u,int fa) {
	::fa[u]=fa;
	d[u]=d[fa]+1;
	sz[u]=1;
	static int lda{0};
	L[u]=++lda;
	fz[lda]=u;
	int p{fa},q{lb[p]},r{lb[q]};
	lb[u]=(d[p]-d[q]!=d[q]-d[r]?p:r);
	for (int _{beg[u]+1};_<=beg[u+1];++_) {
		auto [v,w]{E[_]};
		if (v==fa) continue;
		h[v]=h[u]+w;
		init(v,u);
		sz[u]+=sz[v];
	}
	R[u]=lda;
}
int jump(int u,int de) {
	while (d[u]>de) {
		if (d[lb[u]]<de) u=fa[u];
		else u=lb[u];
	}
	return u;
}
int LCA(int u,int v) {
	if (d[u]<d[v]) swap(u,v);
	u=jump(u,d[v]);
	while (u!=v)
		if (lb[u]==lb[v]) u=fa[u],v=fa[v];
		else u=lb[u],v=lb[v];
	return u;
}
bool isson(int u,int v) { return L[u]<=L[v]&&L[v]<=R[u]; }
LL dis(int u,int v) {
	return h[u]+h[v]-2*h[LCA(u,v)];
}
int n;
int cen;
LL ans;
namespace S {
	LL t[N<<1],tg[N<<1];
	void plant() {
		for (int i{1};i<=n;++i) t[i+n-1]=dis(fz[i],cen),ans+=t[i+n-1];
		for (int i{n-1};i>=1;--i) t[i]=min(t[i<<1],t[i<<1|1]);
	}
	void up(int p) {
		p+=n-1;
		while (p>>=1) t[p]=min(t[p<<1],t[p<<1|1])+tg[p];
	}
	int query() {
		int x{1};
		while (x<n) {
			if (t[x]==t[x<<1]+tg[x]) x<<=1;
			else x=x<<1|1;
		}
		return x-n+1;
	}
	void tag(int p,LL k) {
		t[p]+=k;
		tg[p]+=k;
	}
	void modify(int l,int r,LL v) {
		int l0{l},r0{r};
		for (l+=n-1,r+=n-1;l<=r;l>>=1,r>>=1) {
			if (l&1) t[l]+=v,tg[l]+=v,++l;
			if (~r&1) t[r]+=v,tg[r]+=v,--r;
		}
		up(l0);up(r0);
	}
}
namespace F {
	int t[N+5];
	void init() {
		for (int i{1};i<=n;++i) {
			t[i]=1;
			for (int j{1};j<(i&-i);j<<=1) t[i]+=t[i-j];
		}
	}
	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;
	}
	int kth(int k,int x=0) {
		for (;x;x&=x-1) k+=t[x];
		for (int i{19};i>=0;--i)
			if ((x|1<<i)<=n&&t[x|1<<i]<k)
				k-=t[x|=1<<i];
		return fz[x+1];
	}
}
namespace D {
	int f[N+5],g[N+5];
	void init() {
		iota(f,f+2+n,0);
		iota(g,g+2+n,0);
	}
	void del(int u) {
		f[u]=u+1;
		g[u]=u-1;
	}
	int nxt(int x) {
		while (f[x]!=x) x=f[x]=f[f[x]];
		return (x==n+1?0:fz[x]);
	}
	int pre(int x) {
		while (g[x]!=x) x=g[x]=g[g[x]];
		return fz[x];
	}
}
bool son(int u,int v) { return L[u]<=L[v]&&L[v]<=R[u]; }
int centroid(int k) {
	if (k%2==0) return cen;
	int sz{F::qry(cen)};
	if (sz==k/2) {
		int w{D::nxt(1)},x{D::pre(L[cen]-1)},y{D::nxt(R[cen]+1)},z{D::pre(n)};
		if (!y) {
			int U{LCA(w,x)};
			if (son(U,cen)) return LCA(x,cen);
			else return U;
		} else if (!x) {
			int U{LCA(y,z)};
			if (son(U,cen)) return LCA(y,cen);
			else return U;
		} else {
			int l{LCA(x,cen)},r{LCA(y,cen)};
			return d[l]>d[r]?l:r;
		}
	} else {
		int u{jump(F::kth(k/2+1,L[cen]-1),d[cen]+1)};
		if (F::qry(u)<=k/2) return cen;
		return LCA(D::nxt(L[u]),D::pre(R[u]));
	}
}
int starting_cen(int u,int fa) {
	for (int _{beg[u]+1};_<=beg[u+1];++_) {
		auto [v,w]{E[_]};
		if (v!=fa&&sz[v]*2>n)
			return starting_cen(v,u);
	}
	return u;
}
int U[N+5],V[N+5],W[N+5],X[N+5];
LL res[N+5];
int main() {
	n=read();
	for (int i{1};i<n;++i) {
		U[i]=read();
		V[i]=read();
		W[i]=read();
		++beg[U[i]];++beg[V[i]];
	}
	partial_sum(beg+1,beg+1+n,beg+1);
	copy_n(beg+1,n,X+1);
	for (int i{1};i<n;++i) E[beg[U[i]]--]={V[i],W[i]},E[beg[V[i]]--]={U[i],W[i]};
	init(1,0);
	cen=starting_cen(1,0);
	D::init();
	F::init();
	S::plant();
	for (int i{n-1};i>=1;--i) {
		res[i+1]=ans;
		int z{fz[S::query()]};
		ans-=S::t[1];
		D::del(L[z]);
		F::add(L[z]);
		S::modify(L[z],L[z],1e18);
		int u{cen},v{centroid(i)};
		cerr<<v<<endl;
		if (u!=v) {
			LL d{dis(u,v)};
			ans-=d;
			if (isson(v,u)) {
				S::modify(L[u],R[u],2*d);
				S::tag(1,-d);
			} else if (isson(u,v)) {
				S::modify(L[v],R[v],-2*d);
				S::tag(1,d);
			} else {
				S::modify(L[u],R[u],d);
				S::modify(L[v],R[v],-d);
			}
			cen=v;
		}
	}
	for (int i{2};i<=n;i+=2) write(res[i]);
	fwrite(buf2,01,l2-buf2,stdout);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 38460kb

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: -100
Time Limit Exceeded

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:


result: