/ Randle /

记录详情

Runtime Error


  
# 状态 耗时 内存占用
#1 Wrong Answer 30ms 30.836 MiB
#2 Wrong Answer 31ms 32.125 MiB
#3 Wrong Answer 28ms 32.875 MiB
#4 Wrong Answer 25ms 31.875 MiB
#5 Wrong Answer 28ms 33.0 MiB
#6 Wrong Answer 28ms 31.617 MiB
#7 Wrong Answer 41ms 32.0 MiB
#8 Wrong Answer 230ms 36.441 MiB
#9 Wrong Answer 27ms 32.125 MiB
#10 Wrong Answer 77ms 35.453 MiB
#11 Wrong Answer 125ms 37.535 MiB
#12 Wrong Answer 172ms 41.258 MiB
#13 Wrong Answer 115ms 39.359 MiB
#14 Runtime Error 88ms 42.184 MiB
#15 Runtime Error 131ms 43.961 MiB
#16 Runtime Error 158ms 44.406 MiB
#17 Wrong Answer 427ms 39.477 MiB
#18 Wrong Answer 419ms 38.699 MiB
#19 Wrong Answer 457ms 38.25 MiB
#20 Runtime Error 136ms 44.375 MiB

代码

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>

#include <cstring>
#include <cmath>
#include <string>
#include <cctype>

#include <algorithm>
#include <queue>
#include <stack>

using namespace std;
int N,Q;
int BB[200010],LL[200010];

struct edge{
    int ed,next;
}E[1000100];
int head[200010],Ecnt;
//type
struct mx2{int vv[2];};
struct mx3{int vv[3];}MINUS_INF{-0x3f3f3f3f,-0x3f3f3f3f,-0x3f3f3f3f};
//seg_tree
int fa[200010],size[200010];
int sid[200010],scnt,real[200010];
mx3 T[2000100];
//dp
mx3 f[200010];
// code
inline void addEdge(int st,int ed)
{
    E[++Ecnt].ed=ed;
    E[Ecnt].next=head[st];
    head[st]=Ecnt;
}
inline mx3 merge_mx3(mx3 x,mx3 y)
{
    mx3 ret;
    int a[6];
    memcpy(a,&x,sizeof x),memcpy(a+3,&y,sizeof y);
    sort(a,a+6,greater<int>());
    memcpy(&ret,a,sizeof ret);
    return ret;
}
void dfs(int st)
{
    size[st]=1;
    sid[st]=++scnt;
    real[scnt]=st;
    f[st].vv[0]=BB[st];
    for(int i=head[st];i;i=E[i].next)
    {
        int ed=E[i].ed;
        if(ed!=fa[st])
        {
            fa[ed]=st;
            dfs(ed);
            size[st]+=size[ed];
            f[st]=merge_mx3(f[st],f[ed]);
        }
    }
    //printf("size %d=%d pair[%d,%d]\n",st,size[st],f[st].vv[0],f[st].vv[1]);
}
//seg_tree
void build_tree(int L,int R,int id)
{
    if(L==R)
        T[id].vv[0]=LL[real[L]];
    else
    {
        int mid=(L+R)>>1;
        build_tree(L,mid,id<<1);
        build_tree(mid+1,R,id<<1|1);
        T[id]=merge_mx3(T[id<<1|1],T[id<<1]);
        //T[id]=merge_mx3(T[id],T[id<<1|1]);
    }
}
mx3 query(int B,int E,int L,int R,int id)
{
    if(L>E||R<B||E<B)
        return MINUS_INF;
    if(L>=B&&R<=E)
        return T[id];
    int mid=(L+R)>>1;
    return merge_mx3(query(B,E,L,mid,id<<1) , query(B,E,mid+1,R,id<<1|1));
}
//end of seg_tree
void print_mx3(mx3 t)
{
    printf("%d %d %d\n",t.vv[0],t.vv[1],t.vv[2]);
}
void solve(mx3 mb,mx3 ml)
{
    int ret=mb.vv[1];
    for(int i=1;i<=2;++i)
        for(int j=0;j<=1;++j)
        {
            int tmp=mb.vv[i]+ml.vv[j];
            if(tmp!=mb.vv[0])
                tmp=min(tmp,mb.vv[0]);
            else
                tmp=0;
            ret=max(ret,tmp);
        }
    printf("%d\n",ret);
}
int main()
{
    //mx3 x{1,2,3},y{2,3,4},t;
    //t=merge_mx3(x,y);
    //printf("%d%d%d",t.vv[0],t.vv[1],t.vv[2]);
    scanf("%d%d",&N,&Q);
    for(int i=2;i<=N;++i)
    {
        int x;
        scanf("%d",&x);
        addEdge(i,x);
        addEdge(x,i);
    }
    for(int i=1;i<=N;++i)
        scanf("%d%d",BB+i,LL+i);
    memset(f,0xc0,sizeof f);
    memset(T,0xc0,sizeof T);
    dfs(1);
    build_tree(1,N,1);
    //cout<<sid[3]<<" "<<size[2]<<endl;
    //print_mx3(query(2,2,1,N,1));
    for(int i=1;i<=Q;++i)
    {
        int r;
        scanf("%d",&r);
        mx3 t1,t2;
        t1=f[r];
        t2=merge_mx3( query(sid[1],sid[r]-1,1,N,1) , query(sid[r]+size[r],N,1,N,1) );
        //print_mx3(query(sid[1],sid[r]-1,1,N,1)),print_mx3(query(sid[r]+size[r],N,1,N,1));
        //print_mx3(t1);
        //print_mx3(t2);
        solve(t1,t2);
    }
    return 0;
}

信息

递交者
类型
递交
题目
士兵训练(CQ直辖市noip模拟赛) T3
题目数据
下载
语言
C++
递交时间
2017-11-07 19:11:55
评测时间
2017-11-07 19:12:21
评测机
分数
0
总耗时
2780ms
峰值内存
44.406 MiB