Problem:


Array Update

Problem

項数 N、初項 a、公差 d の等差数列 A がある。以下の形式で数列を更新する命令文が M 個与えられるので、与えられた順序で数列 A を M 回更新したときの K 項目の値を求めよ。

  
i 番目の命令文は3つの整数  xi , yi , zi で表される(1 ≤ i ≤ M)。

xiが0だった場合、yi項目の値と
zi項目の値を入れ替える。

xiが1だった場合、yi項目の値を
zi項目の値に書き換える。 

Input

N
a d
M
x1 y1 z1
x2 y2 z2
...
xM yM zM
K

1行目に、1つの整数 N が与えられる。
2行目に、2つの整数 a と d が空白区切りで与えられる。
3行目に、1つの整数 M が与えられる。

4行目からの M 行のうち i 行目には i 番目の命令文を表す 3 つの整数 xi, yi, zi が空白区切りで与えられる。

最後の行に、1つの整数 K が与えられる。

Constraints

				
1 ≤ N ≤ 108

1 ≤ a ≤ 5

1 ≤ d ≤ 5

1 ≤ M ≤ 10

0 ≤ xi ≤ 1 (1 ≤ i ≤ M)

1 ≤ yi ≤ N (1 ≤ i ≤ M)

1 ≤ zi ≤ N (1 ≤ i ≤ M)

yi &ne; zi (1 ≤ i ≤ M)

1 ≤ K ≤ N

Output

入力で与えられた順番で数列AをM回更新したときのK項目を出力せよ。

Sample Input 1

5
2 3
3
0 2 5
0 3 5
1 2 4
2  

Sample Output 1

11

{  2 ,  5 ,  8 , 11 , 14 }

　             ↓

0 2 5 … 2項目の値と5項目の値を入れ替える

　             ↓

{  2 , 14 ,  8 , 11 ,  5 }

　             ↓

0 3 5 … 3項目の値と5項目の値を入れ替える

　             ↓

{  2 , 14 ,  5 , 11 ,  8 }

　             ↓

1 2 4 … 2項目の値を4項目の値に書き換える

　             ↓

{  2 ,  11 ,  5 , 11 ,  8 }

よって2項目は11である。  

Sample Input 2

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

Sample Output 2

15



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


Sample output:
11

Submission status: Memory Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#B
n = int(input())
a,d = map(int,input().split())
A = []
for i in range(0, n):
    A.append(a + d*i)

m = int(input())

for i in range(m):
    x,y,z = map(int,input().split())

    if x == 0:
        tmp = A[y-1]
        A[y-1] = A[z-1]
        A[z-1] = tmp

    else:
        A[y-1] = A[z-1]

k = int(input())
print(A[k-1])

Submission status: Memory Limit Exceeded

Solution code:
import sys



def init_array(N, a, d):
    return [a+d*n for n in range(N)]

def main():
    N = int(input())
    ins = input().split()
    a = int(ins[0])
    b = int(ins[1])
    M = int(input())
    arrays = init_array(N, a, b)

    for i in range(M):
        ops = [int(x) for x in input().split()]
        ops[1] -= 1
        ops[2] -= 1
        if ops[0] == 0:
            tmp = arrays[ops[1]]
            arrays[ops[1]] = arrays[ops[2]]
            arrays[ops[2]] = tmp
        else:
            arrays[ops[1]] = arrays[ops[2]]
    K = int(input())
    print(arrays[K-1])
    return 0

if __name__ == "__main__":
    sys.exit(main())

Submission status: Memory Limit Exceeded

Solution code:
n = int(input())
a, d = map(int, input().split())
s = [0] + [a + d * i for i in range(n)]
for _ in range(int(input())):
    x, y, z = map(int, input().split())
    if x == 0:s[y], s[z] = s[z], s[y]
    else:s[y] = s[z]
print(s[int(input())])

Submission status: Accepted

Solution code:
# AOJ 1563: Array Update
# Python3 2018.7.13 bal4u

def get(id):
	global a, d
	if id in dic: ans = dic[id]
	else: ans = a + (id-1)*d;
	return ans

dic = {}
N = int(input())
a, d = map(int, input().split())
M = int(input())
for i in range(M):
	x, y, z = map(int, input().split())
	if x == 0:
		vy, vz = get(y), get(z)
		dic[y] = vz
		dic[z] = vy
	else:
		vz = get(z)
		dic[y] = vz
K = int(input())
print(get(K))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N = int(input())
a, d = map(int, input().split())
M = int(input())
data = {}

def get_i(data, i):
    if i in data:
        return data[i]
    else:
        return a + d * i

def data_swap(y, z, data):
    tmp = get_i(data, y)
    data[y] = get_i(data, z)
    data[z] = tmp

def data_write(y, z, data):
    data[y] = get_i(data, z)

for m in range(M):
    # for i in range(5):
    #     print(get_i(data, i))
    # print("---")

    x, y, z = map(int, input().split())
    y -= 1
    z -= 1
    if x == 0:
        data_swap(y, z, data)
    else:
        data_write(y, z, data)

K = int(input())
print(get_i(data, K-1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#B
n = int(input())
a,d = map(int,input().split())
A = []

m = int(input())
x = [0] * m
y = [0] * m
z = [0] * m
NumOfTerms = []

for i in range(m):
    x[i],y[i],z[i] = map(int,input().split())
    NumOfTerms.append(y[i])
    NumOfTerms.append(z[i])

num = set(NumOfTerms)

for i in num:
    A.append([i, a+d*(i-1)])

for i in range(len(x)):
    if x[i] == 0:
        for j in range(len(A)):
            if A[j][0] == y[i]:
                yj = j
            if A[j][0] == z[i]:
                zj = j

        tmp = A[yj][1]
        A[yj][1] = A[zj][1]
        A[zj][1] = tmp

    else:
        for j in range(len(A)):
            if A[j][0] == y[i]:
                yj = j
            if A[j][0] == z[i]:
                zj = j
        A[yj][1] = A[zj][1]

k = int(input())

for j in range(len(num)):
    if A[j][0] == k:
        print(A[j][1])
        exit()

print(a+d*(k-1))

Submission status: Accepted

Solution code:
input()
a, d = map(int, input().split())
x = [tuple(map(int, input().split())) for _ in range(int(input()))]
k = int(input())
for i in x[::-1]:
    if i[0] == 1:
        if i[1] == k:
            k = i[2]
    else:
        if i[1] == k:
            k = i[2]
        elif i[2] == k:
            k = i[1]
print(a + d * (k - 1))

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n = II()
a, b = LI()

m = II()
D = defaultdict(int)
for i in range(m):
    x, y, z = LI()
    y -= 1
    z -= 1
    tmp_y = D[y] if y in D.keys() else a + b * y
    tmp_z = D[z] if z in D.keys() else a + b * z
    if x == 0:
        D[z] = tmp_y

    D[y] = tmp_z

k = II()
k -= 1
print(D[k] if k in D.keys() else a + b * k)

Submission status: Accepted

Solution code:
n = int(input())
a, d = map(int, input().split())
mem = {}


def get_mem(num):
    if num in mem:return mem[num]
    else:return num


m = int(input())
for _ in range(m):
  x, y, z = map(int, input().split())
  if x == 0:
    ny, nz = get_mem(y), get_mem(z)
    mem[y] = nz
    mem[z] = ny
  if x == 1:
    nz = get_mem(z)
    mem[y] = nz
k = get_mem(int(input()))
print(a + d * (k - 1))