Accepted
foo.cc: In function 'void Init()':
foo.cc:18:13: warning: 'char* gets(char*)' is deprecated [-Wdeprecated-declarations]
gets(buf);
^
In file included from /usr/include/c++/7/cstdio:42:0,
from /usr/include/c++/7/ext/string_conversions.h:43,
from /usr/include/c++/7/bits/basic_string.h:6361,
from /usr/include/c++/7/string:52,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from foo.cc:1:
/usr/include/stdio.h:638:14: note: declared here
extern char *gets (char *__s) __wur __attribute_deprecated__;
^~~~
foo.cc:22:17: warning: 'char* gets(char*)' is deprecated [-Wdeprecated-declarations]
gets(buf);
^
In file included from /usr/include/c++/7/cstdio:42:0,
from /usr/include/c++/7/ext/string_conversions.h:43,
from /usr/include/c++/7/bits/basic_string.h:6361,
from /usr/include/c++/7/string:52,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from foo.cc:1:
/usr/include/stdio.h:638:14: note: declared here
extern char *gets (char *__s) __wur __attribute_deprecated__;
^~~~
foo.cc: In function 'int main()':
foo.cc:100:23: warning: 'char* gets(char*)' is deprecated [-Wdeprecated-declarations]
int Test; gets(buf); sscanf(buf,"%d",&Test);
^
In file included from /usr/include/c++/7/cstdio:42:0,
from /usr/include/c++/7/ext/string_conversions.h:43,
from /usr/include/c++/7/bits/basic_string.h:6361,
from /usr/include/c++/7/string:52,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from foo.cc:1:
/usr/include/stdio.h:638:14: note: declared here
extern char *gets (char *__s) __wur __attribute_deprecated__;
^~~~
foo.cc: In function 'void Init()':
foo.cc:18:9: warning: ignoring return value of 'char* gets(char*)', declared with attribute warn_unused_result [-Wunused-result]
gets(buf);
~~~~^~~~~
foo.cc:22:13: warning: ignoring return value of 'char* gets(char*)', declared with attribute warn_unused_result [-Wunused-result]
gets(buf);
~~~~^~~~~
foo.cc: In function 'int main()':
foo.cc:100:19: warning: ignoring return value of 'char* gets(char*)', declared with attribute warn_unused_result [-Wunused-result]
int Test; gets(buf); sscanf(buf,"%d",&Test);
~~~~^~~~~
/tmp/ccXFMvDr.o: In function `Init()':
foo.cc:(.text+0xc): warning: the `gets' function is dangerous and should not be used.
自豪的采用 HydroJudge 进行评测(github.com/hydro-dev/HydroJudge)
正在同步测试数据，请稍后
{"receive":"2020-07-23T09:16:53.132Z","handle":"2020-07-23T09:16:53.132Z","cache_start":"2020-07-23T09:16:53.138Z","read_cases":"2020-07-23T09:16:53.936Z","judge":"2020-07-23T09:16:53.937Z","done":"2020-07-23T09:17:03.756Z"}
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=30009;
const int MAXK=500009;
const int MAXNK=26000000;
int n,k,fa[MAXN],a[MAXN],v[MAXN],sum[MAXN];
int F[MAXNK],G[MAXNK];
int L,R,Que[MAXK],QueV[MAXK];
int deg[MAXN],Node[MAXN];
char buf[30];
void Init(){
gets(buf);
sscanf(buf,"%d%d",&n,&k);
for(int i=0;i<=n+1;i++) deg[i]=0;
for(int i=1;i<=n;i++){
gets(buf);
sscanf(buf,"%d%d%d",&fa[i],&a[i],&v[i]);
if(i>1) deg[fa[i]]++;
}
for(int i=1;i<=n+1;i++) deg[i]+=deg[i-1];
for(int i=2;i<=n;i++) Node[deg[fa[i]]--]=i;
for(int i=1;i<=n;i++) deg[i]=deg[i+1];
}
void PutF(int x,int i,int val){F[x*(k+1)+i]=val;}
int GetF(int x,int i){return F[x*(k+1)+i];}
void RefreshF(int x,int i,int val){PutF(x,i,max(GetF(x,i),val));}
void PutG(int x,int i,int val){G[x*(k+1)+i]=val;}
int GetG(int x,int i){return G[x*(k+1)+i];}
void RefreshG(int x,int i,int val){PutG(x,i,max(GetG(x,i),val));}
void MultiFoldBagF(int x,int y,int ti,int val){
PutF(y,0,0);
if(ti==0){
for(int i=1;i<=k;i++) PutF(y,i,GetF(x,i));
return;
}
Que[L=R=1]=QueV[1]=0;
for(int i=1,v=val;i<=k;i++,v+=val){
if(Que[L]<i-ti)L++;
PutF(y,i,max(GetF(x,i),QueV[L]+v));
int tmp=GetF(x,i)-v;
while(L<=R&&tmp>QueV[R]) R--;
Que[++R]=i;QueV[R]=tmp;
}
}
void MultiFoldBagG(int x,int y,int ti,int val){
Que[L=R=1]=QueV[1]=0;
for(int i=1,v=val;i<=k;i++,v+=val){
if(Que[L]<i-ti)L++;
RefreshG(y,i,QueV[L]+v);
int tmp=GetG(x,i)-v;
while(L<=R&&tmp>QueV[R]) R--;
Que[++R]=i;QueV[R]=tmp;
}
}
void DPF(int fx,int x){
sum[x]=sum[fx]+v[x];
MultiFoldBagF(fx,x,a[x]-1,v[x]);
for(int o=deg[x-1]+1;o<=deg[x];o++){
int y=Node[o];
DPF(x,y);
for(int i=1;i<=k;i++) RefreshF(x,i,GetF(y,i-1)+v[y]);
}
}
void DPG(int fx,int x){
for(int i=0;i<=k;i++) PutG(x,i,GetG(fx,i));
for(int o=deg[x];o>deg[x-1];o--){
int y=Node[o];
DPG(x,y);
MultiFoldBagG(y,x,a[y],v[y]);
}
}
void Solve(){
sum[0]=0;
for(int i=0;i<=k;i++) PutF(0,i,0);
DPF(0,1);
for(int i=0;i<=k;i++) PutG(0,i,0);
DPG(0,1);
int ans=0;
for(int i=1;i<=n;i++)
if(deg[i]==deg[i-1])
for(int j=0;j<=k;j++)
ans=max(ans,GetF(i,j)+GetG(i,k-j)+sum[i]);
cout<<ans<<"\n";
}
int main(){
int Test; gets(buf); sscanf(buf,"%d",&Test);
for(int i=1;i<=Test;i++){
Init();
Solve();
}
}信息
- 递交者
-
CatWigle281 LV 8
- 类型
- 递交
- 题目
- P1015 小Q的苹果树
- 题目数据
- 下载
- 语言
- C++
- 递交时间
- 2020-07-23 17:16:53
- 评测时间
- 2020-07-23 17:16:53
- 评测机
-
undefined
- 分数
- 100
- 总耗时
- 9146ms
- 峰值内存
- 201.426 MiB