質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.34%

最適化による結果の違いの原因を知りたい。

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 822

score 6

前提・実現したいこと

プログラミング学習としてこちらの問題を解こうとしています。
https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0391?year=2018

発生している問題・エラーメッセージ

自分の環境でコードを実行すると正解が出るのですが、サイト上の判定ではWA(wrong answer)が出ます。
最適化の有無が原因だと考えられるのですが、どのような状況下で最適化による影響が出るのか教えていただけると幸いです。

該当のソースコード

#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;
}

試したこと

自分の環境で最適化を施して実行したところ、実行結果が変わりました。(オンラインジャッジと同様になった。)
正解の数値が得られるのですが、オンラインジャッジ上ではすべての数値が0として出力されています。

補足情報(FW/ツールのバージョンなど)

実効環境 gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.12)

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+1

LIST *newnode(void)が返り値を返していないようです。

「最適化で動かなくなる」コードは、ほとんどの場合未定義な動作の領域に突入しているコードを書いて発生します。ここでも、void以外の返り値型を持つ関数が値を返さないので、動作は未定義です。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/05/28 17:51

    返り値を設定したら正常に動作するようになりました。ご指摘いただきありがとうございます。

    キャンセル

0

コードは見てませんが、

どのような状況下で最適化による影響が出るのか

影響が出るのは、
・処理系定義の動作
・未定義の動作
・未規定の動作
に依存するコードになっている場合、つまり規格に準拠した正しいCのプログラムでない場合です。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/05/28 17:51

    maisumakunさんにご指摘いただいたように未定義の動作に依存するコードを作成してしまっていました。
    ご指摘ありがとうございます。今後の参考にいたします。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.34%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る