Submission #62480724

---

Source Code Expand

#include <bits/stdc++.h>
using lint = long long;
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;

std::string k;
std::vector<int> g[N];
int n, s;

bool flag;
int cnt, ed = -1, dis[N], nodes[N];
// dfn 记录遍历到的点

void dfs(int u, int f) {
	nodes[++cnt] = u;
	dis[u] = dis[f] + 1;
	for (auto v : g[u]) {
		if (flag) return ;
		if (dis[v] != INF) { // 环
			ed = v;
			flag = true;
			return ;
		}
		dfs(v, u);
	}
	if (flag) return ;
	--cnt;
}

lint mod(std::string a, lint b) {
	lint res = 0;
	for (auto ch : a) res = (res * 10 + ch - '0') % b;
	return res;
}

bool cmp(const std::string &a, const std::string &b) {
	if (a.size() != b.size()) return a.size() < b.size();
	for (size_t i = 0; i < a.size(); ++i) {
		if (a[i] < b[i]) return true;
	}
	return false;
}

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	std::cin >> n >> s >> k;
	for (int u = 1, v; u <= n; ++u) {
		std::cin >> v;
		g[u].push_back(v);
	}
	memset(dis, 0x3f, sizeof(dis));
	dis[0] = 0;
	
	dfs(s, 0);
	
	//	 从 a 出发没有环，则 k 不可能很大，直接 DFS/ans 直接可以求出
	if (ed == -1 || (k.size() <= 10 && cmp(k, std::to_string(cnt))))
		return std::cout << nodes[stoi(k) + 1] << std::endl, 0;
	
	// 存在环, ed 就是环的起点，在 nodes 中找到 ed 就可确定长度
	int id = -1;
	for (int i = 1; i <= cnt; ++i)
		if (nodes[i] == ed) {
			id = i;
			break;
		}
	
	int len = cnt - id + 1;
	
	int r = (mod(k, len) - (dis[ed] - 2) % len + len) % len;
	
	if (r == 0) r = len;
	
	std::cout << nodes[id + r - 1] << std::endl;
	
	return 0;
}

Submission Info

Judge Result