Submission #201442

#	Time	Username	Problem	Language	Result	Execution time	Memory
201442		ami	Političari (COCI20_politicari)	C++17	70 / 70	31 ms	2300 KiB

politicari

#include <bits/stdc++.h>
#define sz(c)       int(c.size())
#define rep(i,a,b)  for (int i=a; i<(b); ++i)
#define per(i,a,b)  for (int i=(b)-1; i>=(a); --i)
#define fore(c,...) for (auto __VA_ARGS__:(c))
using namespace std;
typedef long long ll;



int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	int N;
	ll K;
	cin>>N>>K;

	vector<vector<int>> a(N,vector<int>(N));
	rep(i,0,N) rep(j,0,N) cin>>a[i][j], a[i][j]--;

	vector<vector<int>> pre(N,vector<int>(N,-1));
	vector<int> ord;
	ord.emplace_back(0);
	ord.emplace_back(1);
	pre[0][1]=0;
	int x=0,y=1,l=1;
	while (pre[y][a[y][x]]==-1) {
		int z=a[y][x];
		pre[y][z]=l++;
		x=y;
		y=z;
		ord.emplace_back(z);
	}

	K--;
	if (K<sz(ord)) {
		cout<<ord[K]+1<<'\n';
		return 0;
	}

	int p=pre[y][a[y][x]];
	K-=p;
	K%=l-p;
	assert(p+K<sz(ord)-1);
	cout<<ord[p+K]+1<<'\n';
}

• Subtask 1: 70 / 70