oj.uz

Submission #475596

# Submission time Handle Problem Language Result Execution time Memory
475596 2021-09-23T08:12:06 Z stefantaga Treasure Hunt (CEOI11_tre) C++14
0 / 100
 236 ms 32936 KB 
#include <bits/stdc++.h>
#include "treinc.h"
using namespace std;
int tata[20][400005];
pair <int,int> intervale[400005];
int lg=19,inainte,j,q;
int acum,niv[400005],lung[400005];
void init()
{
    intervale[++q]={1,1};
    niv[1]=1;
    lung[1]=1;
    acum=2;
}
int cautint(int x)
{
    int st,dr,mij,sol=0;
    st=1;
    dr=q;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (intervale[mij].first<=x)
        {
            sol=mij;
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    return sol;
}
int tatic(int x,int dist)
{
    int acum,i;
    acum=x;
    for (i=0; i<=19; i++)
    {
        if ((dist&(1<<i)))
        {
            acum=tata[i][acum];
        }
    }
    return acum;
}
int lca(int x,int y)
{
    if (niv[x]<niv[y])
    {
        return lca(y,x);
    }
    int dif=niv[x]-niv[y];
    x=tatic(x,dif);
    if (x!=y)
    {
        for (int i=19; i>=0; i--)
        {
            if (tata[i][x]!=tata[i][y])
            {
                x=tata[i][x];
                y=tata[i][y];
            }
        }
        x=tata[0][x];
    }
    return x;
}
void path (int a,int s)
{
    int sal=cautint(a);
    q++;
    intervale[q]={acum,s};
    acum=acum+s;
    tata[0][q]=sal;
    niv[q]=niv[sal]+1;
    lung[q]=lung[sal]+s;
    for (int j=1; j<=19; j++)
    {
        tata[j][q]=tata[j-1][tata[j-1][q]];
    }
}

int dig(int x,int y)
{
    int nod1=cautint(x);
    int nod2=cautint(y);
    int comun=lca(nod1,nod2);
}

Compilation message

tre.cpp: In function 'int dig(int, int)':
tre.cpp:89:9: warning: unused variable 'comun' [-Wunused-variable]
   89 |     int comun=lca(nod1,nod2);
      |         ^~~~~
tre.cpp:90:1: warning: no return statement in function returning non-void [-Wreturn-type]
   90 | }
      | ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 580 KB Output isn't correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 202 ms 31260 KB Output isn't correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 228 ms 7108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 220 ms 21340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 236 ms 32800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 12492 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 32936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 218 ms 32884 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 32872 KB Output isn't correct