提交记录 4366


用户 题目 状态 得分 用时 内存 语言 代码长度
zhaimingshuzms noi18e. 【NOI2018】情报中心 Time Limit Exceeded 15 8 s 5156 KB C++ 1.46 KB
提交时间 评测时间
2018-07-20 17:47:46 2020-07-31 22:56:32
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
//#define int long long
int fi[N],ne[N<<1],b[N<<1],c[N<<1],k,u[N],v[N],fa[N],up[N],deep[N],n,m;
long long vv[N];
void add(int x,int y,int z){
//	cerr<<"add"<<x<<" "<<y<<endl;
	ne[++k]=fi[x]; b[fi[x]=k]=y; c[k]=z;
}
void dfs(int x){
	for (int j=fi[x]; j; j=ne[j])
	if (b[j]!=fa[x]){
		fa[b[j]]=x;
		up[b[j]]=c[j];
		deep[b[j]]=deep[x]+1;
		dfs(b[j]);
	}
}
signed main(){
	freopen("center.in","r",stdin);
	freopen("center.out","w",stdout);
	int t; scanf("%d",&t);
	while (t--){
		scanf("%d",&n); k=0;
		for (int i=1; i<=n; ++i) fi[i]=0;
		for (int i=1; i<n; ++i){
			int x,y,z; scanf("%d%d%d",&x,&y,&z);
			add(x,y,z); add(y,x,z);
		}
		dfs(1);
		long long tans=-1e18;
		scanf("%d",&m);
		for (int i=1; i<=m; ++i){
			scanf("%d%d%lld",&u[i],&v[i],&vv[i]);
			int x=u[i],y=v[i]; long long ans=-vv[i];
			for (int i=1; i<=n; ++i) b[i]=0;
			if (deep[x]>deep[y]) swap(x,y);
			while (deep[x]<deep[y]){
				b[y]=1; ans+=up[y];
				y=fa[y];
			}
			while (x!=y){
				b[x]=1; b[y]=1; ans+=up[x]+up[y];
				x=fa[x]; y=fa[y];
			}
			for (int j=1; j<i; ++j){
				x=u[j]; y=v[j]; long long ans2=-vv[j];
				if (deep[x]>deep[y]) swap(x,y);
				bool fl=0;
				while (deep[x]<deep[y]){
					b[y]?fl=1:ans2+=up[y];
					y=fa[y];
				}
				while (x!=y){
					b[x]?fl=1:ans2+=up[x];
					b[y]?fl=1:ans2+=up[y];
					x=fa[x]; y=fa[y];
				}
				if (fl) tans=max(tans,ans+ans2);
			}
		}
		if (tans==-1e18) puts("F"); else 
		printf("%lld\n",tans);
	}
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #172.72 us76 KBAcceptedScore: 5

Testcase #2401.77 us76 KBAcceptedScore: 5

Testcase #316.373 ms80 KBAcceptedScore: 5

Testcase #48 s200 KBTime Limit ExceededScore: 0

Testcase #58 s1 MB + 84 KBTime Limit ExceededScore: 0

Testcase #68 s5 MB + 36 KBTime Limit ExceededScore: 0

Testcase #78 s784 KBTime Limit ExceededScore: 0

Testcase #88 s2 MB + 320 KBTime Limit ExceededScore: 0

Testcase #98 s2 MB + 248 KBTime Limit ExceededScore: 0

Testcase #108 s680 KBTime Limit ExceededScore: 0

Testcase #118 s2 MB + 240 KBTime Limit ExceededScore: 0

Testcase #128 s2 MB + 252 KBTime Limit ExceededScore: 0

Testcase #138 s584 KBTime Limit ExceededScore: 0

Testcase #148 s616 KBTime Limit ExceededScore: 0

Testcase #158 s328 KBTime Limit ExceededScore: 0

Testcase #168 s2 MB + 216 KBTime Limit ExceededScore: 0

Testcase #178 s844 KBTime Limit ExceededScore: 0

Testcase #188 s2 MB + 340 KBTime Limit ExceededScore: 0

Testcase #198 s2 MB + 264 KBTime Limit ExceededScore: 0

Testcase #208 s2 MB + 464 KBTime Limit ExceededScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2026-04-13 16:29:49 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠