TLE*1+WA*6
查看原帖
TLE*1+WA*6
407417
HerikoDeltana楼主2021/5/31 11:40

RT,没查出来错(

#include <bits/stdc++.h>
#define Heriko return
#define Deltana 0
#define Romano 1
#define S signed
#define U unsigned
#define LL long long
#define R register
#define I inline
#define D double
#define LD long double
#define mst(a, b) memset(a, b, sizeof(a))
#define ON std::ios::sync_with_stdio(false)
using namespace std;
I void fr(LL & x)
{
    LL f = 1;
    char c = getchar();
    x = 0;
    while (c < '0' || c > '9') 
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') 
    {
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    x *= f;
}
I void fw(LL x)
{
    if(x<0) putchar('-'),x=-x;
    static LL stak[50];
    LL top=0;
    do
    {
        stak[top++]=x%10;
        x/=10;
    }
    while(x);
    while(top) putchar(stak[--top]+'0');
    putchar('\n');
}
const int MXX=6e5+10;
struct HRiver2
{
    LL to,nex;
}e[MXX<<1];
LL hd[MXX],tot;
LL dep[MXX],f[MXX][35],lg[MXX];
LL n,m,s;
I void ade(LL x,LL y)
{
    e[++tot].to=y;
    e[tot].nex=hd[x];
    hd[x]=tot;
    Heriko;
}
void DFS(LL x,LL y)
{
    f[x][0]=y;dep[x]=dep[y]+1;
    for(R LL i=1;i<=lg[dep[x]];i++) f[x][i]=f[f[x][i-1]][i-1];
    for(R LL i=hd[x];i;i=e[i].nex) if(e[i].to!=y) DFS(e[i].to,x);
    Heriko;
}
I LL LCA(LL x,LL y)
{
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]) x=f[x][lg[dep[x]-dep[y]]-1];
    if(x==y) Heriko x;
    for(LL i=lg[dep[x]]-1;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    Heriko f[x][0];
}
I void loging()
{
    for(LL i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1] == 1);
    Heriko;
}
S main()
{
    LL x,y;
    fr(n),fr(m),fr(s);
    for(R LL i=1;i<n;i++)
    {
        fr(x),fr(y);
        ade(x,y);
        ade(y,x);
    }
    loging();
    DFS(s,0);
    for(R LL i=1;i<=m;i++) 
    {   
        fr(x),fr(y);
        fw(LCA(x,y)); 
    }
    Heriko Deltana;
}

感谢各位(

2021/5/31 11:40
加载中...