D_1 - On/Off Switch

典型問題です。頂点を倍加してダブリングします。
各マスにつてスイッチがOFF状態のマスとON状態のマスで $2N$ 個の頂点にします。
そして各頂点から有効辺を $1$ 本ずつ張ります(functional-graph)。

類題

• 頂点倍加 : ABC277 E - Crystal Switches
• ダブリング : abc179 E - Sequence Sum

def decimal_to_nAry(num_10,n): #10進数からn進数へ変換する(n<=36) |int型 => str型
    str_n = []
    while num_10:
        if num_10%n >= 10:
            str_n.append(chr(num_10%n+55))
        else:
            str_n.append(str(num_10%n))
        num_10 //= n
    return "".join(str_n[::-1])

n,m,k = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
sC = set(C)

dv = [[0 for j in range(2*n)]for i in range(60)]

for i in range(n):
    if(A[i] in sC):
        dv[0][i] = A[i]-1+n
    else:
        dv[0][i] = A[i]-1
    if(B[i] in sC):
        dv[0][n+i] = B[i]-1
    else:
        dv[0][n+i] = B[i]-1+n

for i in range(1,60):
    for j in range(2*n):
        dv[i][j] = dv[i-1][dv[i-1][j]]

K = decimal_to_nAry(k,2)[::-1]
v = 0
for i in range(len(K)):
    if(K[i]=="1"):
        v = dv[i][v]

print(v%n+1)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
	ll n, m, k;
	cin >> n >> m >> k;
	vector<int> a(n), b(n), c(n);
	for(int i = 0; i < n; i++){
		cin >> a[i];
		a[i]--;
	}
	for(int i = 0; i < n; i++){
		cin >> b[i];
		b[i]--;
	}
	for(int i = 0; i < m; i++){
		int C;
		cin >> C;
		C--;
		c[C] = 1; 
	}

	vector DB(60, vector(n * 2, 0));
	for(int i = 0; i < 2 * n; i++){
		DB[0][i] = (i & 1) ? b[i/2] * 2 + 1 - c[b[i/2]] : a[i/2] * 2 + c[a[i/2]];
	}
	for(int i = 1; i < 60; i++){
		for(int j = 0; j < 2 * n; j++){
			DB[i][j] = DB[i-1][DB[i-1][j]];
		}
	}

	int pos = 0;
	for(int i = 0; i < 60; i++){
		if((1LL << i) & k) pos = DB[i][pos];
	}

	cout << pos / 2 + 1 << endl;
}

別解

周期性を利用して $O(N)$ で解くことが出来ます。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    int n, m;
    ll k;
    cin >> n >> m >> k;

    vector<int> a(n), b(n);
    vector<bool> switch_exists(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        b[i]--;
    }
    for (int i = 0; i < m; i++) {
        int c;
        cin >> c;
        c--;
        switch_exists[c] = 1;
    }

    vector<vector<int>> order(n, vector<int>(2, -1));
    vector<vector<int>> v;

    pair<int, int> now = {0, 0};
    int s;

    for (;;) {
        auto [i, is_on] = now;

        if (order[i][is_on] >= 0) {
            s = order[i][is_on];
            break;
        }

        order[i][is_on] = v.size();
        v.push_back({i, is_on});

        int to;
        if (is_on)
            to = b[i];
        else
            to = a[i];

        if (switch_exists[to]) is_on ^= 1;

        now = {to, is_on};
    }

    if (k <= s) {
        cout << v[k][0] + 1 << endl;
        return 0;
    }

    k -= s;
    k %= (v.size() - s);
    k += s;

    cout << v[k][0] + 1 << endl;
}