//#define NDEBUG
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define F first
#define S second
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
if(pvaspace) b << " "; pvaspace=true;\
b << pva;\
}\
b << "\n";}
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tiii tuple<int, int, int>
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) ((a) / (b) + !!((a) % (b)))
//#define TEST
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
using namespace __gnu_pbds;
const ll MOD = 1000000007;
const ll MAX = 2147483647;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.F << ',' << p.S << ')';
}
int main(){
StarBurstStream
int n; ll k;
cin >> n >> k; k--;
vector<vector<int>> g(n + 1, vector<int>(n + 1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) cin >> g[j][i];
}
int lst = 1;
vector<vector<bool>> b(n + 1, vector<bool>(n + 1));
int now = 2;
vector<int> ans;
ans.eb(1);
while(true){
ans.eb(now);
if(b[lst][now]) break;
b[lst][now] = true;
int tmp = g[lst][now];
lst = now;
now = tmp;
}
// printv(ans, cerr);
if(k < ans.size()){
cout << ans[k] << "\n";
return 0;
}
k -= (int)ans.size() - 1;
ans.clear();
b.clear();
b.resize(n + 1, vector<bool>(n + 1));
while(true){
if(b[lst][now]) break;
ans.eb(now);
b[lst][now] = true;
int ttt = g[lst][now];
lst = now;
now = ttt;
}
// printv(ans, cerr);
cout << ans[k % ans.size()] << "\n";
return 0;
}
Compilation message
politicari.cpp: In function 'int main()':
politicari.cpp:75:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(k < ans.size()){
~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
9 ms |
760 KB |
Output is correct |
3 |
Correct |
18 ms |
1400 KB |
Output is correct |
4 |
Correct |
23 ms |
1912 KB |
Output is correct |
5 |
Correct |
27 ms |
2296 KB |
Output is correct |
6 |
Correct |
27 ms |
2296 KB |
Output is correct |
7 |
Correct |
4 ms |
376 KB |
Output is correct |
8 |
Correct |
6 ms |
508 KB |
Output is correct |
9 |
Correct |
11 ms |
760 KB |
Output is correct |
10 |
Correct |
23 ms |
1912 KB |
Output is correct |
11 |
Correct |
28 ms |
2296 KB |
Output is correct |
12 |
Correct |
25 ms |
2296 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
6 ms |
504 KB |
Output is correct |