JOIの過去問について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
platypus
記事: 2
登録日時: 3年前

JOIの過去問について

#1

投稿記事 by platypus » 3年前

初めまして、platypusと申します。

練習のために去年のJOIの本選の過去問をAOJなどのサービスを使いながら解いていたのですが、
3問目の「鉄道運賃」がどうしても入力17でWrongAnswerになってしまいます。
こちらが提出後のジャッジです。
http://judge.u-aizu.ac.jp/onlinejudge/r ... =2015906#2

解説スライドやほかの回答者のコードを見ながら、
グラフを適切に管理し首都からの距離を求めた後、有効な辺について削除処理を組んだつもりなのですが、
どうやら不満を持つ都市がなぜか多く見積もられているケースがあるようです。

そのため、クエリを処理する部分(提出したコードの//Solve For Queryの部分)を特に重点的にチェックしたのですが、
入力自体がとても長いこともあり、デバッグ作業も行き詰りにあるのが現状です。
ヒントや予測でも構いません、間違っている可能性のある箇所を指摘してもらえればと思います。
以下が提出したコードとなります。

コード:

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
 
using namespace std;
using pint = pair<int, int>;
 
#define In_(x) scanf("%d",&x)
 
int n, m, q;
int u[200000], v[200000];
vector<pint>graph[100000];
int dist[100000];
int parnum[100000];
bool alive[100000];
set<int>answer;
 
int main()
{
    //Input
    In_(n);
    In_(m);
    In_(q);
    for (int i = 0; i < m; ++i)
    {
        int u_, v_;
        In_(u_); In_(v_);
        --u_; --v_;
        u[i] = u_; v[i] = v_;
        graph[u_].push_back({ v_,i });
        graph[v_].push_back({ u_,i });
    }
    //BFS
    fill(parnum, parnum + n, 0);
    fill(dist, dist + n, -1);
    dist[0] = 0;
    queue<int> que;
    que.push(0);
    while (!que.empty())
    {
        int p = que.front(); que.pop();
        for (auto rawq : graph[p])
        {
            int next = rawq.first;
            if (dist[next] == -1)
            {
                dist[next] = dist[p] + 1;
                que.push(next);
                ++parnum[next];
            }
            else if (dist[next] == dist[p] + 1)
            {
                ++parnum[next];
            }
        }
    }
    //Solve For Query
    fill(alive, alive + n, true);
    for (int k = 0; k < q; ++k)
    {
        int qur; In_(qur);
        --qur;
        if (dist[v[qur]] != dist[u[qur]])
        {
            queue<int>que;
            int pus = v[qur];
            if (dist[v[qur]] < dist[u[qur]])pus = u[qur];
            que.push(pus);
            while (!que.empty())
            {
                int vec = que.front(); que.pop();
                if (!alive[vec])continue;
                --parnum[vec];
                if (parnum[vec] == 0)
                {
                    answer.emplace(vec);
                    alive[vec] = false;
                    for (auto to : graph[vec])
                    {
                        if (dist[to.first] == dist[vec] + 1 && alive[to.first])
                        {
                            que.push(to.first);
                        }
                    }
                }
            }
        }
        printf("%d\n", answer.size());
    }
    return 0;
}
VC++を使ってコードを書きましたが、環境の変化による入出力の変化は(多分)ないと思われます。

C++自体はある程度使っているものの、競技プログラミングはまだまだな状態です。
お手柔らかにお願いいたします…

“C言語何でも質問掲示板” へ戻る