/ Randle /

记录详情

Runtime Error


  
# 状态 耗时 内存占用
#1 Accepted 109ms 41.461 MiB
#2 Accepted 106ms 39.875 MiB
#3 Accepted 117ms 39.25 MiB
#4 Accepted 112ms 39.625 MiB
#5 Accepted 117ms 39.875 MiB
#6 Accepted 101ms 41.625 MiB
#7 Accepted 123ms 40.602 MiB
#8 Accepted 281ms 44.848 MiB
#9 Accepted 34ms 42.125 MiB
#10 Accepted 82ms 44.125 MiB
#11 Accepted 127ms 44.875 MiB
#12 Accepted 169ms 46.434 MiB
#13 Accepted 134ms 45.375 MiB
#14 Runtime Error 96ms 50.137 MiB
#15 Runtime Error 109ms 50.637 MiB
#16 Runtime Error 153ms 52.812 MiB
#17 Accepted 536ms 47.191 MiB
#18 Accepted 570ms 46.625 MiB
#19 Accepted 573ms 46.301 MiB
#20 Accepted 550ms 50.941 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 mx4{int vv[4];}MINUS_INF{-0x3f3f3f3f,-0x3f3f3f3f,-0x3f3f3f3f,-0x3f3f3f3f};
//seg_tree
int fa[200010],size[200010];
int sid[200010],scnt,real[200010];
mx4 T[2000100];
//dp
mx4 f[200010];
// code
inline void addEdge(int st,int ed)
{
    E[++Ecnt].ed=ed;
    E[Ecnt].next=head[st];
    head[st]=Ecnt;
}
inline mx4 merge_mx4(mx4 x,mx4 y)
{
    mx4 ret=MINUS_INF;
    int pa=0,pr=0;
    static int a[8];
    memcpy(a,&x,sizeof x),memcpy(a+4,&y,sizeof y);
    sort(a,a+8,greater<int>());
    //int t=unique(a,a+6)-a-1;
    //memcpy(&ret,a,min(sizeof ret,sizeof(int)*(t+1)));
    while(pr<4&&pa<8)
    {
        if(pa==0||a[pa]!=a[pa-1]||(pa==1&&a[pa]==a[pa-1]))
            ret.vv[pr++]=a[pa];
        pa++;
    }

    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_mx4(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_mx4(T[id<<1|1],T[id<<1]);
        //T[id]=merge_mx4(T[id],T[id<<1|1]);
    }
}
mx4 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_mx4(query(B,E,L,mid,id<<1) , query(B,E,mid+1,R,id<<1|1));
}
//end of seg_tree
void print_mx4(mx4 t)
{
    printf("%d %d %d %d\n",t.vv[0],t.vv[1],t.vv[2],t.vv[3]);
}
void solve(mx4 mb,mx4 ml)
{
    int ret=0;
    for(int i=1;i<=3;++i)
        for(int j=0;j<=3;++j)
        {
            int tmp=max(mb.vv[i],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",max(ret,0));
}
int main()
{
    //freopen("1.txt","w+",stdout);
    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);
    //printf("\t%d   %d\n",LL[real[1]],real[1]);
    //print_mx4( query(1,1,1,N,1) );
    for(int i=1;i<=Q;++i)
    {
        int r;
        scanf("%d",&r);
        mx4 t1,t2;
        t1=f[r];
        t2=merge_mx4( query(sid[1],sid[r]-1,1,N,1) , query(sid[r]+size[r],N,1,N,1) );
        //print_mx4(query(sid[1],sid[r]-1,1,N,1)),print_mx4(query(sid[r]+size[r],N,1,N,1));
        //print_mx4(t1);
        //print_mx4(t2);
        solve(t1,t2);
    }
    return 0;
}

信息

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