#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#warning Check Integer OverFlow
#define ll long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define trav(a,b) for(auto a:b)
#define sz(a) a.size()
#define maxs(a,b) if(b>a)a=b
#define mins(a,b) if(b<a)a=b
#ifdef LOCAL
#define dbg(x) cerr<<"["<<#x<<":"<<x<<"] "
#define dbg2(a,b) dbg(a);dbg(b)
#define dbg3(a,b,c) dbg2(a,b);dbg(c)
#define dln cerr << ln
#else
#define dbg(x) 0
#define dbg2(a,b) 0
#define dbg3(a,b,c) 0
#define dln 0
#endif
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (((a)/(__gcd(a,b))) * b)
#define print(arr) for(auto it = arr.begin();it < arr.end();it ++){cout << *it << " ";}cout << ln;
#define all(a) (a).begin(), (a).end()
#define vi vector<int>
#define v vector
#define p pair
#define pii p<int,int>
#define pb push_back
#define mk make_pair
#define f first
#define s second
#define ln "\n"
typedef long double ld;
using namespace std;
using namespace __gnu_pbds;
ll modF=1e9+7;
template<class T> using iset = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;
/*OUTPUT
*/
ll n,k;
ll a[500][500];
bool vis[500][500];
vector<pii> cycle;
pii start;
void dfs(int i,int j){
if(vis[i][j]){
start = mk(i,j);
return;
}
cycle.pb(mk(i,j));
vis[i][j] = true;
dfs(a[i][j] - 1,i);
}
void solve(){
cin >> n >> k;
rep(i,0,n){
rep(j,0,n){
cin >> a[i][j];
vis[i][j] = false;
}
}
if(k == 1){
cout << 1 << ln;
return;
}
k --;
// dbg("yes");
dfs(1,0);
int time = 0;
for(auto e:cycle){
if(e != start){
time ++;
}
else{
break;
}
}
int cl = sz(cycle) - time;
// dbg(cl);
// dbg(time);
// dbg(k);
if(k <= time){
// dbg("yes");
cout << cycle[k - 1].f + 1 << ln;
}
else{
k --;
cout << cycle[(k - time) % cl + time].f + 1 << ln;
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int t = 1;
// cin >> t;
while(t --){
solve();
}
}
Compilation message
politicari.cpp:4:2: warning: #warning Check Integer OverFlow [-Wcpp]
4 | #warning Check Integer OverFlow
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1644 KB |
Output is correct |
| 3 |
Correct |
14 ms |
2668 KB |
Output is correct |
| 4 |
Correct |
16 ms |
3052 KB |
Output is correct |
| 5 |
Correct |
20 ms |
3436 KB |
Output is correct |
| 6 |
Correct |
20 ms |
3436 KB |
Output is correct |
| 7 |
Correct |
1 ms |
492 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1516 KB |
Output is correct |
| 10 |
Correct |
17 ms |
3308 KB |
Output is correct |
| 11 |
Correct |
20 ms |
3436 KB |
Output is correct |
| 12 |
Correct |
20 ms |
3564 KB |
Output is correct |
| 13 |
Correct |
1 ms |
620 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1004 KB |
Output is correct |
