Submission #732191

#	Time	Username	Problem	Language	Result	Execution time	Memory
732191		Koful123	Političari (COCI20_politicari)	C++17	30 / 70	21 ms	8504 KiB

politicari

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

void solve(){

	int n,k;
	cin >> n >> k; --k;

	vector<vector<int>> v(n),vis(n);
	for(int i = 0; i < n; i++){
		v[i].assign(n,0); vis[i].assign(n,-1);
		for(int j = 0; j < n; j++){
			cin >> v[i][j];
		}
	}

	vector<int> cyc(1,0);

	int last = 0,cur = 1;
	while(vis[last][cur] == -1){
		vis[last][cur] = cyc.size() - 1;
		cyc.push_back(cur);
		int tmp = last; last = cur;
		cur = v[cur][tmp] - 1;	
	}

	assert(k <= 1e5);

	cyc.pop_back();
	if(k <= vis[last][cur]){
		cout << 1 + cyc[vis[last][cur]] << endl;
		return;
	}

	else k -= vis[last][cur];

	vector<int> nw;
	for(int i = vis[last][cur]; i < cyc.size(); i++){
		nw.push_back(cyc[i]);
	}

	cout << 1 + nw[k % nw.size()] << endl;
}
 
signed main(){ 

	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int t = 1;
//	cin >> t;
 
	while(t--)
		solve();
 	
	return 0;
}

Compilation message (stderr)

politicari.cpp: In function 'void solve()':
politicari.cpp:45:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i = vis[last][cur]; i < cyc.size(); i++){
      |                              ~~^~~~~~~~~~~~

• Subtask 1: 30 / 70