Tarjan + Cartesian Tree MLE70pts球条

ENJOuYang @ 2024-10-03 18:34:47

#include "bits/stdc++.h"
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}
const int maxn=2e7+5,maxm=2e7+5;
int arr[maxn],fa[maxn],stk[maxn],ch[maxn][2],top;
int nxt[maxm<<1],to[maxm<<1],hd[maxn],cnt=1;
static inline void addq(int u,int v){nxt[++cnt]=hd[u],to[cnt]=v,hd[u]=cnt;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
unsigned long long ans=0;
void tarjan(int cu,int f) {
    fa[cu]=cu;
    if(ch[cu][0]) tarjan(ch[cu][0],cu);
    if(ch[cu][1]) tarjan(ch[cu][1],cu);
    for(int i=hd[cu];i;i=nxt[i]) {
        if(fa[to[i]]) {
            stk[i>>1]=arr[find(to[i])];
        }
    }
    fa[cu]=f;
}
int main() {
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    srand(k);
    for(int i=1;i<=n;++i) {
        arr[i]=read();
//      printf("%d\n",arr[i]);
        while(top&&arr[stk[top]]<arr[i])
            ch[i][0]=stk[top--];
        if(top) ch[stk[top]][1]=i;
        stk[++top]=i;
    }
    for(int i=1;i<=m;++i) {
        int u=read()%n+1,v=read()%n+1;
//      printf("%d %d\n",u,v);
        addq(u,v);
        addq(v,u);
    }
    tarjan(stk[1],stk[1]);
    for(int i=1;i<=m;++i) ans+=stk[i];
    printf("%llu",ans);
    return 0;
}

by ENJOuYang @ 2024-10-03 18:35:27

玄关

by ENJOuYang @ 2024-10-03 19:13:49

根据空间编程，结果TLE60pts

// Please pay attention to the memory limit: 500 Mb
#include "bits/stdc++.h"
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}
const int maxn=2e7+5,maxm=5e6+5;
int arr[maxn],fa[maxn],stk[maxn],ch[maxn][2],top;
int nxt[maxm<<1],to[maxm<<1],hd[maxn],cnt=1;
static inline void addq(int u,int v){nxt[++cnt]=hd[u],to[cnt]=v,hd[u]=cnt;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
unsigned long long ans=0;
void tarjan(int cu,int f) {
    fa[cu]=cu;
    if(ch[cu][0]) tarjan(ch[cu][0],cu);
    if(ch[cu][1]) tarjan(ch[cu][1],cu);
    for(int i=hd[cu];i;i=nxt[i]) {
        if(fa[to[i]]) {
            stk[i>>1]=arr[find(to[i])];
        }
    }
    fa[cu]=f;
}
int main() {
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    srand(k);
    for(int i=1;i<=n;++i) {
        arr[i]=read();
//      printf("%d\n",arr[i]);
        while(top&&arr[stk[top]]<arr[i])
            ch[i][0]=stk[top--];
        if(top) ch[stk[top]][1]=i;
        stk[++top]=i;
    }
    int pos=stk[1],__m=m/4;
    for(int i=1;i<=3;++i) {
        cnt=1;
        std::fill(hd+1,hd+n+1,0);
        for(int i=1;i<=__m;++i) {
            int u=read()%n+1,v=read()%n+1;
    //      printf("%d %d\n",u,v);
            addq(u,v);
            addq(v,u);
        }
        tarjan(pos,pos);
        for(int i=1;i<=m;++i) ans+=stk[i];
    }
    cnt=1;
    std::fill(hd+1,hd+n+1,0);
    for(int i=3*__m+1;i<=m;++i) {
        int u=read()%n+1,v=read()%n+1;
        addq(u,v);
        addq(v,u);
    }
    tarjan(pos,pos);
    for(int i=1;i<=m;++i) ans+=stk[i];
    printf("%llu",ans);
    return 0;
}