# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
731454 | eneskav | Političari (COCI20_politicari) | C++17 | 17 ms | 4204 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <cstring>
#define int long long
using namespace std;
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
signed main()
{
fastio;
int n, k;
cin >> n >> k;
int a[n + 1][n + 1];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
cin >> a[i][j];
if (k <= 2)
{
cout << k;
return 0;
}
int vis[n + 1][n + 1];
memset(vis, 0, sizeof(vis));
int p = 0, c = 1;
vector<int> v;
v.push_back(1);
a[c][p] = 2;
int cycle = 0;
for (int i = 1; i < k * 3; ++i)
{
int t = c;
c = a[c][p];
p = t;
if (vis[c][p])
{
cycle = vis[c][p];
v.pop_back();
break;
}
vis[c][p] = i;
v.push_back(c);
}
// print v
/* for (auto i : v)
cout << i << " ";
cout << endl; */
--cycle;
// cout << "cycle " << cycle << endl;
// cout << "cycle length " << v.size() - cycle << endl;
if (k < v.size())
{
cout << v[k - 1];
return 0;
}
// cout << v[((k - cycle) - 1) % (v.size() - cycle)];
// the code above is wrong, it should be like this
cout << v[(k - cycle - 1) % (v.size() - cycle) + cycle];
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |