Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

鉄道運賃(Train Fare)

JOI 国には $N$ 個の都市があり，それぞれ $1, 2, ..., N$ の番号が付けられている．都市 1 はJOI 国の首都である．

また，JOI 国には鉄道会社がひとつだけあり，この会社は $M$ 個の路線を運行している．これらの路線にはそれぞれ $1, 2, ..., M$ の番号が付けられており，$i$ 番目 $(1 \leq i \leq M)$ の路線は都市 $U_i$ と都市 $V_i$ を双方向に結んでいる．都市と都市の間を鉄道以外で移動することはできない．また，どの都市からどの都市へもいくつかの路線を乗り継いで移動することができるようになっている．

現在，どの路線の運賃も 1 円である．経営不振に陥った鉄道会社は，今後 $Q$ 年間かけていくつかの路線の運賃を値上げする計画を立てた．この計画では，計画開始から $j$ 年目$(1 \leq j \leq Q)$ の年初めに路線 $R_j$ の運賃を 1 円から 2 円に値上げする予定である．値上げされた路線の運賃は，その後ずっと2 円のままであり，再び値上げすることはない．

ところで，この鉄道会社では，毎年，各都市の住民の満足度調査を行っている．計画開始前は，どの都市の住民もこの鉄道会社に満足しているが，値上げによって不満を持つ住民が現れる可能性がある．

それぞれの年の満足度調査は，その年の値上げの実施後に行う．したがって， $j$ 年目$(1 \leq j \leq Q)$ の満足度調査は，路線 $R_1, R_2, ... , R_j$ の運賃の値上げは完了し，それ以外の路線の運賃は値上げされていない状態で行われることになる． $j$ 年目$(1 \leq j \leq Q)$ の満足度調査では，都市 $k$ $(2 \leq k \leq N)$ の住民は，以下の条件が満たされるとき，そしてそのときに限り鉄道会社に不満を抱く．

 その時の運賃で都市 $k$ から首都である都市 $1$ へ移動するときの費用の最小値が，計画開始前の運賃で都市 $k$ から都市 $1$ へ移動するときの費用の最小値よりも大きい．

ただし，いくつかの路線を使って移動するときの費用は，それぞれの路線の運賃の合計である．また，都市 $1$ の住民が鉄道会社に対して不満を抱くことはない．値上げ後の運賃で最小の費用を達成する経路は，計画開始前の運賃で最小の費用を達成する経路と異なる可能性があることに注意せよ．

計画の実行に先立って，今後 $Q$ 年間の住民の満足度調査それぞれにおいて，鉄道会社に不満を抱く住民がいる都市の数を計算しておきたい．

課題

JOI 国の鉄道路線の情報と，運賃の値上げ計画が与えられたとき，それぞれの満足度調査において鉄道会社に不満を抱く住民がいる都市の数を求めるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

 1 行目には，3 個の整数 $N, M, Q$ が空白を区切りとして書かれている．これらは，JOI 国には $N$ 個の都市と $M$ 個の路線があり，運賃の値上げ計画が $Q$ 年間に渡ることを表している．

 続く $M$ 行のうちの $i$ 行目$(1 \leq i \leq M)$ には，2 個の整数 $U_i$, $V_i$ が空白を区切りとして書かれている．これらは，$i$ 番目の路線が都市 $U_i$ と都市 $V_i$ を結んでいることを表している．

 続く $Q$ 行のうちの $j$ 行目$(1 \leq j \leq Q)$ には，整数 $R_j$ が書かれている．これは，計画の $j$ 年目に路線 $R_j$ の運賃を値上げすることを表している．

出力

標準出力に $Q$ 行で出力せよ． $j$ 行目$(1 \leq j \leq Q)$ には， $j$ 年目の満足度調査で不満を抱く住民がいる都市の数を出力せよ．

制限

すべての入力データは以下の条件を満たす．

 $2 \leq N \leq 100 000$ 

 $1 \leq Q \leq M \leq 200 000$ 

 $1 \leq U_i \leq N$ $(1 \leq i \leq M)$ 

 $1 \leq V_i \leq N$ $(1 \leq i \leq M)$ 

 $U_i \ne V_i$ $(1 \leq i \leq M)$ 

 $1 \leq R_j \leq M$ $(1 \leq j \leq Q)$ 

 $R_j \ne R_k$ $(1 \leq j 時点都市2     都市3     都市4     都市5    

計画開始前     1 1 2 2

1 年目1 1 2 2

2 年目1 2 2 3

3 年目1 2 2 3

4 年目2 2 3 3

5 年目2 2 4 3

例えば，3 年目の満足度調査では，都市 $3$ と都市 $5$ の住民が不満を抱くので，出力の 3 行目には 2 を出力する．

入力例2

4 6 6
1 2
1 3
1 4
2 3
2 4
3 4
1
4
2
5
3
6

出力例2

1
1
2
2
3
3

入力例3

2 1 1
1 2
1

出力例3

1

第15回 日本情報オリンピック本選 課題   2016 年 2 月 14 日



Sample input:
5 6 5
1 2
1 3
4 2
3 2
2 5
5 3
5
2
4
1
3


Sample output:
0
2
2
4
4

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from collections import deque

class UnionFind:
    def __init__(self,size):
        self.parent=range(size)
        self.tree_num=size
        self.tree_w=[1]*size
        self.rank=[0]*size

    def findset(self,x):
        if self.parent[x]==x:
            return x
        else:
            self.parent[x]=self.findset(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x=self.findset(x)
        y=self.findset(y)
        if x==y:
            return
        if self.rank[x]<self.rank[y]:
            self.parent[x]=y
            self.tree_num-=1
            self.tree_w[y]+=self.tree_w[x]
        else:
            self.parent[y]=x
            self.tree_num-=1
            self.tree_w[x]+=self.tree_w[y]
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

    def same(self,x,y):
        if self.findset(x)==self.findset(y):
            return True
        else:
            return False

    def tree_number(self):
        return self.tree_num

    def tree_weight(self,x):
        return self.tree_w[self.findset(x)]

n,m,q=map(int,raw_input().split())
e=[]
g=[[] for _ in xrange(n)]
for i in xrange(m):
    u,v=map(int,raw_input().split())
    u-=1;v-=1
    e.append((u,v))
    g[u].append(v)
    g[v].append(u)
d=[10000000]*n
d[0]=0
dq=deque([0])
while len(dq)>0:
    now=dq.popleft()
    for nx in g[now]:
        if d[nx]>d[now]+1:
            dq.append(nx)
            d[nx]=d[now]+1

r=[int(raw_input()) for _ in xrange(q)]
pe=deepcopy(e)
for i in xrange(q):
    r[i]-=1
    pe[r[i]]=(-1,-1)

uf=UnionFind(n)
for i in xrange(m):
    u,v=pe[i]
    if u==-1 and v==-1:continue
    uf.unite(u,v)
ans=[0]*(q+1)
ans[q]=n-uf.tree_weight(0)
cnt=ans[q]
for i in xrange(q-1,-1,-1):
    u,v=e[r[i]]
    if abs(d[v]-d[u])==0:
        ans[i]=cnt
        continue
    unum=uf.tree_weight(u)
    vnum=uf.tree_weight(v)
    if not uf.same(0,u) and not uf.same(0,v):
        uf.unite(u,v)
        ans[i]=cnt
    else:
        if uf.same(0,u) and uf.same(0,v):
            ans[i]=cnt
        elif uf.same(0,u):
            uf.unite(u,v)
            cnt-=vnum
            ans[i]=cnt
        else:
            uf.unite(u,v)
            cnt-=unum
            ans[i]=cnt

for i in xrange(1,q+1):
    print ans[i]

Submission status: Wrong Answer

Solution code:
from collections import deque

def make_DAG(s,n,g):
    newg=[[] for _ in xrange(n)]
    dist=[float("inf")]*n
    dist[0]=0
    dq=deque([s])
    visited=[False]*n
    indeg=[0]*n
    while len(dq)>0:
        now=dq.popleft()
        for nx in g[now]:
            if dist[nx]>=dist[now]+1:
                if not visited[nx]:
                     visited[now]=True
                     dq.append(nx)
                newg[now].append(nx)
                dist[nx]=dist[now]+1
                indeg[nx]+=1
    return newg,dist,indeg

def bfs_count(s,n,g,indeg):
    cnt=0
    if indeg[s]<=0: return cnt
    dq=deque([s])
    while len(dq)>0:
        now=dq.popleft()
        indeg[now]-=1
        if indeg[now]==0:
            cnt+=1
            for nx in g[now]:
                dq.append(nx)
    return cnt

n,m,q=map(int,raw_input().split())
e=[]
g=[[] for _ in xrange(n)]
for i in xrange(m):
    u,v=map(int,raw_input().split())
    u-=1;v-=1
    g[u].append(v)
    g[v].append(u)
    e.append((u,v))
DAG,dist,indeg=make_DAG(0,n,g)
ans=0
for i in xrange(q):
    r=int(raw_input())
    r-=1
    u,v=e[r]
    if abs(dist[u]-dist[v])!=1:
        print ans
        continue
    if dist[u]<dist[v]:
        ans+=bfs_count(v,n,DAG,indeg)
    else:
        ans+=bfs_count(u,n,DAG,indeg)
    print ans

Submission status: Wrong Answer

Solution code:
from collections import deque

def make_DAG(s,n,g):
    newg=[[] for _ in xrange(n)]
    dist=[float("inf")]*n
    dist[0]=0
    dq=deque([s])
    visited=[False]*n
    visited[0]=True
    indeg=[0]*n
    while len(dq)>0:
        now=dq.popleft()
        for nx in g[now]:
            if dist[nx]>=dist[now]+1:
                if not visited[nx]:
                     visited[nx]=True
                     dq.append(nx)
                newg[now].append(nx)
                dist[nx]=dist[now]+1
                indeg[nx]+=1
    return newg,dist,indeg

def bfs_count(s,n,g,indeg):
    cnt=0
    if indeg[s]<=0: return cnt
    dq=deque([s])
    while len(dq)>0:
        now=dq.popleft()
        indeg[now]-=1
        if indeg[now]==0:
            cnt+=1
            for nx in g[now]:
                dq.append(nx)
    return cnt

n,m,q=map(int,raw_input().split())
e=[]
g=[[] for _ in xrange(n)]
for i in xrange(m):
    u,v=map(int,raw_input().split())
    u-=1;v-=1
    g[u].append(v)
    g[v].append(u)
    e.append((u,v))
DAG,dist,indeg=make_DAG(0,n,g)
ans=0
for i in xrange(q):
    r=int(raw_input())
    r-=1
    u,v=e[r]
    if abs(dist[u]-dist[v])!=1:
        print ans
        continue
    if dist[u]<dist[v]:
        ans+=bfs_count(v,n,DAG,indeg)
    else:
        ans+=bfs_count(u,n,DAG,indeg)
    print ans

Submission status: Wrong Answer

Solution code:
from collections import deque

def make_DAG(s,n,g):
    newg=[[] for _ in xrange(n)]
    dist=[float("inf")]*n
    dist[s]=0
    dq=deque([s])
    visited=[False]*n
    visited[s]=True
    indeg=[0]*n
    while len(dq)>0:
        now=dq.popleft()
        for nx in g[now]:
            if dist[nx]>=dist[now]+1:
                if not visited[nx]:
                     visited[nx]=True
                     dq.append(nx)
                newg[now].append(nx)
                dist[nx]=dist[now]+1
                indeg[nx]+=1
    return newg,dist,indeg

def bfs_count(s,DAG,indeg):
    indeg[s]-=1
    if indeg[s]!=0:return 0
    dq=deque([s])
    cnt=1
    while len(dq)>0:
        now=dq.popleft()
        for nx in DAG[now]:
            indeg[nx]-=1
            if indeg[nx]==0:
                cnt+=1
                dq.append(nx)
    return cnt

n,m,q=map(int,raw_input().split())
e=[]
g=[[] for _ in xrange(n)]
for i in xrange(m):
    u,v=map(int,raw_input().split())
    u-=1;v-=1
    g[u].append(v)
    g[v].append(u)
    e.append((u,v))
DAG,dist,indeg=make_DAG(0,n,g)
ans=0
for i in xrange(q):
    r=int(raw_input())
    r-=1
    u,v=e[r]
    if abs(dist[u]-dist[v])==0:
        print ans
        continue
    if dist[u]<dist[v]:
        ans+=bfs_count(v,DAG,indeg)
    else:
        ans+=bfs_count(u,DAG,indeg)
    print ans

Submission status: Accepted

Solution code:
from collections import deque

def make_DAG(s,n,g):
    newg=[[] for _ in xrange(n)]
    dist=[float("inf")]*n
    dist[s]=0
    dq=deque([s])
    visited=[False]*n
    visited[s]=True
    indeg=[0]*n
    while len(dq)>0:
        now=dq.popleft()
        for nx in g[now]:
            if dist[nx]>=dist[now]+1:
                if not visited[nx]:
                     visited[nx]=True
                     dq.append(nx)
                newg[now].append(nx)
                dist[nx]=dist[now]+1
                indeg[nx]+=1
    return newg,dist,indeg

def bfs_count(s,DAG,indeg):
    indeg[s]-=1
    if indeg[s]!=0:return 0
    dq=deque([s])
    cnt=1
    while len(dq)>0:
        now=dq.popleft()
        for nx in DAG[now]:
            if ok.has_key((now,nx)):continue
            ok[(now,nx)]=True
            indeg[nx]-=1
            if indeg[nx]==0:
                cnt+=1
                dq.append(nx)
    return cnt

n,m,q=map(int,raw_input().split())
e=[]
g=[[] for _ in xrange(n)]
for i in xrange(m):
    u,v=map(int,raw_input().split())
    u-=1;v-=1
    g[u].append(v)
    g[v].append(u)
    e.append((u,v))
DAG,dist,indeg=make_DAG(0,n,g)
ans=0
ok={}
for i in xrange(q):
    r=int(raw_input())
    r-=1
    u,v=e[r]
    if abs(dist[u]-dist[v])==0:
        print ans
        continue
    if dist[u]<dist[v]:
        if not ok.has_key((u,v)):
            ok[(u,v)]=True
            ans+=bfs_count(v,DAG,indeg)
    else:
        if not ok.has_key((v,u)):
            ok[(v,u)]=True
            ans+=bfs_count(u,DAG,indeg)
    print ans

Submission status: Runtime Error

Solution code:
from copy import deepcopy
from collections import deque

n,m,q=map(int,raw_input().split())
e=[]
g1=[[] for _ in xrange(n)]
for i in xrange(m):
    u,v=map(int,raw_input().split())
    u-=1;v-=1
    g1[u].append(v)
    g1[v].append(u)
    e.append((u,v))
d1=[10**9]*n
d1[0]=0
dq=deque([0])
while len(dq)>0:
    now=dq.popleft()
    for nx in g1[now]:
        if d1[nx]>d1[now]+1:
            dq.append(nx)
            d1[nx]=d1[now]+1

pe=deepcopy(e)
qu=[]
for i in xrange(q):
    r=int(raw_input())
    r-=1
    pe[r]=(-1,-1)
    qu.append(r)
g2=[[] for _ in xrange(n)]
for i in xrange(m):
    u,v=pe[i]
    if u==-1 and v==-1:continue
    g2[u].append(v)
    g2[v].append(u)
d2=[10**9]*n
d2[0]=0
dq=deque([0])
while len(dq)>0:
    now=dq.popleft()
    for nx in g2[now]:
        if d2[nx]>d2[now]+1:
            dq.append(nx)
            d2[nx]=d2[now]+1
            
def dfs(now):
    global cnt
    ok[now]=True
    cnt+=1
    for nx in g2[now]:
        if not ok[nx] and d2[now]+1==d1[nx]:
            d2[nx]=d2[now]+1
            dfs(nx)
    return

cnt=0
ok=[False]*n
for i in xrange(n):
    if d1[i]==d2[i]:
        cnt+=1
        ok[i]=True
ans=[0]*(q+1)
ans[q]=n-cnt
for i in xrange(q-1,-1,-1):
    r=qu[i]
    u,v=e[r]
    if (d2[u]!=10**9 and d2[u]==d2[v]) or (ok[u] and ok[v]):
        ans[i]=n-cnt
        continue
    if not ok[u] and not ok[v]:
        ans[i]=n-cnt
        g2[u].append(v)
        g2[v].append(u)
        continue
    if ok[u]:
        g2[u].append(v)
        g2[v].append(u)
        if d2[u]+1==d1[v]:
            d2[v]=d2[u]+1
            dfs(v)
    else:
        g2[u].append(v)
        g2[v].append(u)
        if d2[v]+1==d1[u]:
            d2[u]=d2[v]+1
            dfs(u)
    ans[i]=n-cnt
for i in xrange(1,q+1):
    print ans[i]

Submission status: Runtime Error

Solution code:
from copy import deepcopy
from collections import deque
from sys import setrecursionlimit


n,m,q=map(int,raw_input().split())
e=[]
g1=[[] for _ in xrange(n)]
for i in xrange(m):
    u,v=map(int,raw_input().split())
    u-=1;v-=1
    g1[u].append(v)
    g1[v].append(u)
    e.append((u,v))
d1=[10**9]*n
d1[0]=0
dq=deque([0])
while len(dq)>0:
    now=dq.popleft()
    for nx in g1[now]:
        if d1[nx]>d1[now]+1:
            dq.append(nx)
            d1[nx]=d1[now]+1

pe=deepcopy(e)
qu=[]
for i in xrange(q):
    r=int(raw_input())
    r-=1
    pe[r]=(-1,-1)
    qu.append(r)
g2=[[] for _ in xrange(n)]
for i in xrange(m):
    u,v=pe[i]
    if u==-1 and v==-1:continue
    g2[u].append(v)
    g2[v].append(u)
d2=[10**9]*n
d2[0]=0
dq=deque([0])
while len(dq)>0:
    now=dq.popleft()
    for nx in g2[now]:
        if d2[nx]>d2[now]+1:
            dq.append(nx)
            d2[nx]=d2[now]+1

setrecursionlimit(10**8)            
def dfs(now):
    global cnt
    ok[now]=True
    cnt+=1
    for nx in g2[now]:
        if not ok[nx] and d2[now]+1==d1[nx]:
            d2[nx]=d2[now]+1
            dfs(nx)
    return

cnt=0
ok=[False]*n
for i in xrange(n):
    if d1[i]==d2[i]:
        cnt+=1
        ok[i]=True
ans=[0]*(q+1)
ans[q]=n-cnt
for i in xrange(q-1,-1,-1):
    r=qu[i]
    u,v=e[r]
    if (d2[u]!=10**9 and d2[u]==d2[v]) or (ok[u] and ok[v]):
        ans[i]=n-cnt
        continue
    if not ok[u] and not ok[v]:
        ans[i]=n-cnt
        g2[u].append(v)
        g2[v].append(u)
        continue
    if ok[u]:
        g2[u].append(v)
        g2[v].append(u)
        if d2[u]+1==d1[v]:
            d2[v]=d2[u]+1
            dfs(v)
    else:
        g2[u].append(v)
        g2[v].append(u)
        if d2[v]+1==d1[u]:
            d2[u]=d2[v]+1
            dfs(u)
    ans[i]=n-cnt
for i in xrange(1,q+1):
    print ans[i]