練習のために去年の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;
}
C++自体はある程度使っているものの、競技プログラミングはまだまだな状態です。
お手柔らかにお願いいたします…