Submission #526347

#	Time	Username	Problem	Language	Result	Execution time	Memory
526347		bebecanvas	Političari (COCI20_politicari)	C++14	70 / 70	21 ms	3212 KiB

politicari

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define endl '\n'
#define sz(x) (int) (x).size()

signed main(){
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	
	int n, k; cin >> n >> k;
	int g[505][505];
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cin >> g[i][j];
		}
	}
	
	vector<int> v;
	v.push_back(1); v.push_back(2);
	set<pair<int, int> > s; s.insert(make_pair(1, 2));
	map<pair<int, int>, int> m; m[make_pair(1, 2)]= 0;
	
	int start= -1;
	int end= -1;
	while(true){
		int size= sz(v);
		int a= v[size-1];
		int b= v[size-2];
		int c= g[a][b];
		if(s.count(make_pair(a, c))){
			start= m[make_pair(a, c)];
			end= size-2;
			break;
		}
		v.push_back(c);
		s.insert(make_pair(a, c));
		m[make_pair(a, c)]= size-1;
	}
	
	//cout << start << endl;
	//cout << end << endl;
	vector<int> p;
	for(int i= start; i<=end; i++){p.push_back(v[i]);}
	
	if(k<start){cout << v[k-1] << endl;}
	else{
		int left= k- start;
		//cout << "left " << left << endl;
		left%= sz(p);
		//cout << "sz(p) " << sz(p) << endl;
		//cout << "left " << left << endl;
		left--;
		if(left==-1){left= sz(p)-1;}
		cout << p[left] << endl;
	}
}

• Subtask 1: 70 / 70