Submission #5546151


Source Code Expand

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=200010;
int n,m,q,tot,tot2,cnt,tmp,ans;
int f[maxn][20];
int head[maxn];
ll aa[maxn],l;
ll dis[maxn];
int dfn[maxn],d[maxn];
int dep[maxn],e[maxn],pos[maxn];
int ok[maxn];
bool vis[maxn];
struct node
{
    int to,nex;
    ll w;
}a[maxn];
void add(int u,int v,ll w)
{
    //cout<<u<<"->"<<v<<endl;
    a[cnt].to=v;
    a[cnt].w=w;
    a[cnt].nex=head[u];
    head[u]=cnt++;
}
void init()
{
    cnt=tot=tot2=0;
    for(int i=0;i<=2*n;i++)
    {
        head[i]=-1;pos[i]=-1;
        vis[i]=0;
        ok[i]=0;
    }
    dis[1]=0;
}
void dfs(int u,int deep)//1
{
    if(pos[u]!=-1)return;
    dfn[tot2]=u;d[u]=tot2++;
    pos[u]=tot;e[tot]=u;dep[tot++]=deep;
    for(int i=head[u];i!=-1;i=a[i].nex)
    {
        int v=a[i].to;
        if(pos[v]==-1)
        {
            dis[v]=dis[u]+a[i].w;
            dfs(v,deep+1);
            e[tot]=u;dep[tot++]=deep;
        }
    }
}
void rmq(int n)//2
{
    for(int i=1;i<=n;i++)f[i][0]=i;
    for(int j=1;(1<<j)<=n;j++)
    for(int i=1;i+(1<<j)-1<=n;i++)
    {
        if(dep[f[i][j-1]]<dep[f[i+(1<<(j-1))][j-1]]) f[i][j]=f[i][j-1];
        else f[i][j]=f[i+(1<<(j-1))][j-1];
    }
}
int RMQ(int l,int r)
{
    int k=(int)(log((double)(r-l+1))/log(2.0));
    if(dep[f[l][k]]<dep[f[r-(1<<k)+1][k]]) return f[l][k];
    else return f[r-(1<<k)+1][k];
}
int lca(int x,int y)//3
{
    if(pos[x]<pos[y]) return e[RMQ(pos[x],pos[y])];
    else return e[RMQ(pos[y],pos[x])];
}
ll cal(int x,int y)
{
    return dis[x]+dis[y]-2*dis[lca(x,y)];
}
int main()
{
    int T,cas=1;
    while(scanf("%d",&n)!=EOF)
    {
        init();
        for(int i=1;i<=n;i++)
        scanf("%lld",&aa[i]);
        scanf("%lld",&l);
        for(int i=1;i<=n;i++)
        if(!ok[i]){
            int j=i,k=i;
            while(k<n)
            {
                while(j+1<=n&&aa[j+1]-aa[k]<=l)
                {
                    j++;
                    if(ok[j])
                    {
                        ok[k]=j;
                        add(k,j,1LL);
                        add(j,k,1LL);
                        k=n;
                        break;
                    }
                }
                if(k==n) break;
                if(!ok[j])
                {
                    ok[j]=k;ok[k]=j;
                    add(k,j,1LL);
                    add(j,k,1LL);
                }
                k=j;
            }
        }
        //printf("Case #%d:\n",cas++);
        dfs(1,0);
        rmq(2*n-1);//4
        ll ans=0;
        scanf("%d",&q);
        while(q--)
        {
            int u,v;
            scanf("%d %d",&u,&v);
            ans=cal(u,v);
            if(llabs(aa[u]-aa[v])<=l) ans=1;
            printf("%lld\n",ans);
        }
    }
    return 0;
}

Submission Info

Submission Time
Task E - Tak and Hotels
User IGVA
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2934 Byte
Status WA
Exec Time 3155 ms
Memory 33024 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:87:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&aa[i]);
                             ^
./Main.cpp:88:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&l);
                         ^
./Main.cpp:120:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&q);
                       ^
./Main.cpp:124:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d",&u,&v);
                                 ^

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 200 0 / 500
Status
AC × 1
AC × 5
WA × 9
AC × 7
WA × 19
TLE × 1
Set Name Test Cases
Sample example_01.txt
Subtask1 example_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt
All example_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt
Case Name Status Exec Time Memory
example_01.txt AC 7 ms 10880 KB
subtask1_01.txt WA 3 ms 10496 KB
subtask1_02.txt AC 3 ms 10496 KB
subtask1_03.txt WA 4 ms 10496 KB
subtask1_04.txt AC 4 ms 10496 KB
subtask1_05.txt WA 4 ms 10496 KB
subtask1_06.txt AC 3 ms 10496 KB
subtask1_07.txt WA 3 ms 10496 KB
subtask1_08.txt AC 4 ms 10496 KB
subtask1_09.txt WA 4 ms 10496 KB
subtask1_10.txt WA 4 ms 10496 KB
subtask1_11.txt WA 4 ms 10496 KB
subtask1_12.txt WA 4 ms 10496 KB
subtask1_13.txt WA 4 ms 10496 KB
subtask2_01.txt WA 77 ms 28544 KB
subtask2_02.txt AC 80 ms 33024 KB
subtask2_03.txt WA 86 ms 28160 KB
subtask2_04.txt AC 2149 ms 22912 KB
subtask2_05.txt WA 50 ms 23296 KB
subtask2_06.txt TLE 3155 ms 11776 KB
subtask2_07.txt WA 80 ms 28672 KB
subtask2_08.txt WA 80 ms 31488 KB
subtask2_09.txt WA 78 ms 31488 KB
subtask2_10.txt WA 80 ms 31488 KB
subtask2_11.txt WA 74 ms 30336 KB
subtask2_12.txt WA 68 ms 33024 KB
subtask2_13.txt WA 2518 ms 28032 KB