Home>

I am trying to solve this problem as a programming learning.

When I execute the code in my environment, the correct answer comes out, but the judgment on the site gives WA (wrong answer).
It is thought that this is due to the presence or absence of optimization, but I would appreciate it if you could tell me under what circumstances optimization will affect you.

Applicable source code
#include<stdio.h>
#include<stdlib.h>
#define N_MAX 100010
int parent [100005];
int depth [100005];
int dist [100005];
int p [30] [100005];
typedef struct lst
{
    struct lst * next;
    int to;
    int cost;
} LIST;
LIST list [N_MAX];
LIST * newnode (void)
{
    LIST * p;
    p = malloc (sizeof (LIST));
    if (p! = NULL)
    {
        p->next = NULL;
    }
}
LIST * add (LIST * p, int to, int cost)
{
    while (p->next! = NULL)
    {
        p = p->next;
    }
    if ((p->next = newnode ())! = NULL)
    {
        p->to = to;
        p->cost = cost;
    }
    return p;
}
int max (int a, int b)
{
    return a>b? a: b;
}
int min (int a, int b)
{
    return b>a? a: b;
}
void swap (int * a, int * b)
{
    int temp;
    temp = * a;
    * a = * b;
    * b = temp;
}

void dfs (int pos, int prev, int Depth, int Dist)
{
    parent [pos] = prev;
    depth [pos] = Depth;
    dist [pos] = Dist;
    LIST * p;
    for (p =&list [pos];p->next! = NULL;p = p->next) {
        LIST e;
        e.to = p->to;
        e.cost = p->cost;
        if (e.to == prev)
            continue;
        dfs (e.to, pos, Depth + 1, Dist + e.cost);
    }
    return;
}
int lca (int a, int b)
{
    if (depth [a]>depth [b])
        swap (&a,&b);
    int s = (depth [b]-depth [a]);
    for (int i = 0;i<30;i ++)
        if (s >>i&1)
            b = p [i] [b];
    if (a == b)
        return a;
    for (int i = 29;i>= 0;i--)
    {
        if (p [i] [a]! = p [i] [b])
        {
            a = p [i] [a];
            b = p [i] [b];
        }
    }
    return parent [a];
}
int calc_dist (int a, int b)
{
    int c = lca (a, b);
    return dist [a]-dist [c] + dist [b]-dist [c];
}
int check (int p, int a, int b, int c)
{
    int res = 0;
    res = max (res, calc_dist (p, a));
    res = max (res, calc_dist (p, b));
    res = max (res, calc_dist (p, c));
    return res;
}
int solve (int a, int b, int c)
{
    int x = lca (b, c);
    if (calc_dist (x, b)>calc_dist (x, c))
        swap (&b,&c);
    int y = calc_dist (b, c)/2;
    int z = c;
    for (int i = 29;i>= 0;i--)
    {
        int nz = p [i] [z];
        if (nz! = -1&&(dist [c]-dist [nz])<= y)
        {
            z = nz;
        }
    }
    int res = check (z, a, b, c);
    if (parent [z]! = -1)
        res = min (res, check (parent [z], a, b, c));
    return res;
}
int main (void)
{
    int N, Q;
    int u, v, w;
    int a, b, c;
    scanf ("% d% d",&N,&Q);
    for (int i = 1;i<N;i ++)
    {
        scanf ("% d% d% d",&u,&v,&w);
        u--;
        v--;
        add (&list [u], v, w);
        add (&list [v], u, w);
    }
    dfs (1, -1, 0, 0);
    for (int i = 0;i<N;i ++)
        p [0] [i] = parent [i];
    for (int i = 1;i<30;i ++)
    {
        for (int j = 0;j<N;j ++)
        {
            int x = p [i-1] [j];
            if (x! = -1)
                x = p [i-1] [x];
            p [i] [j] = x;
        }
    }
    for (int i = 0;i<Q;i ++)
    {
        scanf ("% d% d% d",&a,&b,&c);
        a--;
        b--;
        c--;
        int ans = (1<<30);
        ans = min (ans, solve (a, b, c));
        ans = min (ans, solve (b, a, c));
        ans = min (ans, solve (c, b, a));
        printf ("% d \ n", ans);
    }
    return 0;
}
What I tried

When I ran it with optimization in my environment, the execution result changed. (It became the same as the online judge.)
I can get the correct number, but all the numbers are output as 0 on the online judge.

Supplemental information (FW/tool version, etc.)

Effective environment gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1 ~ 16.04.12)

  • Answer # 1

    LIST * newnode (void)Does not seem to return a return value.

    Code that is "stuck on optimization" is almost alwaysUndefined behaviorIt is caused by writing code that plunges into the area of. even here,voidThe behavior is undefined because functions with return types other than return no values.

  • Answer # 2

    I haven't seen the code,

      

    Under what circumstances can optimization be affected?

    The impact is that
    -Processor-defined behavior
    ・ Undefined behavior
    ・ Unspecified operation
    If the code depends on, that is, it is not a valid standard C program.