QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#355456 | #5111. Take On Meme | ucup-team052# | WA | 117ms | 3816kb | C++23 | 1.7kb | 2024-03-16 18:07:13 | 2024-03-16 18:07:14 |
Judging History
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'