Submission #526347

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526347	2022-02-14T13:04:00 Z	bebecanvas	Političari (COCI20_politicari)	C++14	70 / 70	21 ms	3212 KB

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.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2640 KB	Output is correct
2	Correct	4 ms	2508 KB	Output is correct
3	Correct	10 ms	2828 KB	Output is correct
4	Correct	14 ms	3084 KB	Output is correct
5	Correct	16 ms	3200 KB	Output is correct
6	Correct	15 ms	3212 KB	Output is correct
7	Correct	1 ms	2252 KB	Output is correct
8	Correct	3 ms	2380 KB	Output is correct
9	Correct	5 ms	2508 KB	Output is correct
10	Correct	15 ms	3056 KB	Output is correct
11	Correct	17 ms	3168 KB	Output is correct
12	Correct	21 ms	3148 KB	Output is correct
13	Correct	1 ms	2308 KB	Output is correct
14	Correct	3 ms	2380 KB	Output is correct