QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#431433#7419. Jiry Matchingsxyloph0nex17RE 0ms0kbC++142.5kb2024-06-05 15:39:192024-06-05 15:39:19

Judging History

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

  • [2024-06-05 15:39:19]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-06-05 15:39:19]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define sz(v) ((int)v.size())
using namespace std;
const int MAXN=2e5+5;
const ll inf=1e18;
typedef vector<ll> poly;
typedef array<array<poly,2>,2> mat;
poly max(poly f,poly g) {
	if(f.size()<g.size()) f.swap(g);
	for(int i=0;i<sz(g);++i) f[i]=max(f[i],g[i]);
	return f;
}
poly operator *(poly f,poly g) {
	if(f.empty()&&g.empty()) return {};
	poly h(sz(f)+sz(g)-1);
	int i=1,j=1,k=1; h[0]=f[0]+g[0];
	while(i<sz(f)&&j<sz(g)) {
		if(f[i]-f[i-1]>g[j]-g[j-1]) h[k]=h[k-1]+f[i]-f[i-1],++i,++k;
		else h[k]=h[k-1]+g[j]-g[j-1],++j,++k;
	}
	while(i<sz(f)) h[k]=h[k-1]+f[i]-f[i-1],++i,++k;
	while(j<sz(g)) h[k]=h[k-1]+g[j]-g[j-1],++j,++k;
	assert(k==sz(f)+sz(g)-1);
	return h;
}
poly operator +(poly f,ll k) {
	for(ll &x:f) x+=k;
	f.insert(f.begin(),-inf);
	return f;
}
poly dp[MAXN][2]; //0:unlimit, 1:empty
mat mul(mat x,mat y,ll z) {
	mat w;
	for(int i:{0,1}) for(int j:{0,1}) {
		w[i][j]=max(x[i][0]*y[0][j],x[i][1]*y[1][j]+z);
	}
	return w;
}
struct Edge { int v,w; };
vector <Edge> G[MAXN];
int siz[MAXN],hson[MAXN],fw[MAXN],Fa[MAXN];
void dfs0(int u,int fz) {
	siz[u]=1,Fa[u]=fz;
	for(auto e:G[u]) if(e.v^fz) {
		fw[e.v]=e.w,dfs0(e.v,u),siz[u]+=siz[e.v];
		if(siz[e.v]>siz[hson[u]]) hson[u]=e.v;
	}
}
mat f[MAXN];
void clr(mat &z) { for(int i:{0,1}) for(int j:{0,1}) poly().swap(z[i][j]); }
void calc(int l,int r,const vector<int> &id) {
	if(l==r) {
		f[l][0][0]=dp[id[l]][0];
		f[l][0][1]=f[l][1][0]=dp[id[l]][1];
		return ;
	}
	int s=0;
	for(int i=l;i<=r;++i) s+=dp[id[i]][0].size();
	for(int x=l+1,t=sz(dp[id[l]][0]);x<=r;++x) {
		t+=sz(dp[id[x]][0]);
		if(2*t<=s) continue;
		calc(l,x-1,id),calc(x,r,id);
		f[l]=mul(f[l],f[x],fw[id[x]]),clr(f[x]);
		return ;
	}
	assert(0);
}
vector <int> hc[MAXN];
void dfs1(int u,int top) {
	dp[u][0]=dp[u][1]={0};
	for(auto e:G[u]) if(e.v!=Fa[u]&&e.v!=hson[u]) dfs1(e.v,e.v);
	if(u==1) return ;
	hc[top].push_back(u);
	if(hson[u]) dfs1(hson[u],top);
	if(u!=top) return ;
	calc(0,sz(hc[u])-1,hc[u]);
	int p=Fa[u];
	//auto qqq=dp[p][1]*f[0][1][0]+fw[u];
	dp[p][0]=max(dp[p][0]*f[0][0][0],dp[p][1]*f[0][1][0]+fw[u]);
	dp[p][1]=dp[p][1]*f[0][0][0];
	for(int i=0;i<sz(hc[u]);++i) clr(f[i]);
}
signed main() {
	int n;
	scanf("%d",&n);
	for(int i=1,u,v,w;i<n;++i) {
		scanf("%d%d%d",&u,&v,&w);
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	dfs0(1,0),hson[1]=0,dfs1(1,1);
	for(int i=1;i<sz(dp[1][0]);++i) printf("%lld ",dp[1][0][i]);
	for(int i=sz(dp[1][0]);i<n;++i) printf("? "); puts("");
	return 0;
}

详细

Test #1:

score: 0
Runtime Error

input:

5
1 2 3
2 3 5
2 4 4
3 5 2

output:


result: