oj.uz

답안 #526347

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526347 2022-02-14T13:04:00 Z bebecanvas Političari (COCI20_politicari) C++14
70 / 70
 21 ms 3212 KB 
#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

# 결과 실행 시간 메모리 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