QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#355456#5111. Take On Memeucup-team052#WA 117ms3816kbC++231.7kb2024-03-16 18:07:132024-03-16 18:07:14

Judging History

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

  • [2024-03-16 18:07:14]
  • 评测
  • 测评结果:WA
  • 用时:117ms
  • 内存:3816kb
  • [2024-03-16 18:07:13]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#else
#define D(...) ((void)0)
#endif
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;

using LL=long long;
const int INF=0X3F3F3F3F;
mt19937_64 rng(0);

const int N=10005;

int n,A,B;

LL dp[N];
vector<int>e[N];
int X[N][2],Y[N][2];
LL mn[N],mx[N];

int dfn[N],idx;
void dfs(int u){
	dfn[++idx]=u;
	for(auto&x:e[u]){
		dfs(x);
	}
}

int main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif

	cin>>n;
	rep(i,1,n){
		int x;
		cin>>x;
		if(x){
			e[i].resize(x);
			rep(j,0,x-1){
				cin>>e[i][j];
			}
		}else{
			cin>>X[i][0]>>Y[i][0];
			X[i][1]=X[i][0];
			Y[i][1]=Y[i][0];
		}
	}
	
	dfs(1);
	
	LL ans=0;
	
	rep(tc,1,1000000){
		A=(rng()%int(2e9))-1e9;
		B=(rng()%int(2e9))-1e9;
		per(_,n,1){
			int u=dfn[_];
			if(e[u].empty()){
				mn[u]=mx[u]=LL(A)*X[u][0]+LL(B)*Y[u][0];
			}else{
				LL t=-1e18;
				int id=-1;
				LL t_=1e18;
				int id_=-1;
				mx[u]=0;
				mn[u]=0;
				
				X[u][0]=X[u][1]=Y[u][0]=Y[u][1]=0;
				for(auto&x:e[u]){
					if(mn[x]+mx[x]>t){
						t=mn[x]+mx[x];
						id=x;
					}
					if(mn[x]+mx[x]<t_){
						t_=mn[x]+mx[x];
						id_=x;
					}
					mx[u]-=mn[x];
					mn[u]-=mx[x];
					X[u][0]-=X[x][1];
					Y[u][0]-=Y[x][1];
					
					X[u][1]-=X[x][1];
					Y[u][1]-=Y[x][1];
				}
				mn[u]+=t_;
				mx[u]+=t;
				
				X[u][0]+=X[id][1]+X[id][0];
				Y[u][0]+=Y[id][1]+Y[id][0];
				
				X[u][1]+=X[id_][1]+X[id_][0];
				Y[u][1]+=Y[id_][1]+Y[id_][0];
				
			}
		}
		ans=max(ans,LL(X[1][0])*X[1][0]+LL(Y[1][0])*Y[1][0]);
	}
	
	printf("%lld\n",ans);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 41ms
memory: 3760kb

input:

5
4 2 3 4 5
0 2 -2
0 1 3
0 4 -6
0 -18 5

output:

725

result:

ok single line: '725'

Test #2:

score: 0
Accepted
time: 35ms
memory: 3816kb

input:

5
2 2 3
2 4 5
0 1 5
0 -4 -6
0 -1 7

output:

340

result:

ok single line: '340'

Test #3:

score: -100
Wrong Answer
time: 117ms
memory: 3776kb

input:

18
3 4 3 2
2 5 6
3 7 9 8
3 10 11 12
0 4 -1
0 18 49
0 -2 10
2 13 14
0 -5 6
0 5 8
4 15 16 17 18
0 17 3
0 3 -9
0 -7 -1
0 14 -33
0 -23 11
0 11 14
0 2 19

output:

22525

result:

wrong answer 1st lines differ - expected: '26269', found: '22525'