Here is the problem link D - Teleporter . I tried solving the problem without using any Graph Theory algorithm by just using a Set as a major tool. Here’s the idea, begin exploring from the first city and store that current city in a set. Now, keep exploring and add the cities that you haven’t explored yet to the set, and simply stop when you encounter a city that is already in the set because you have found a cycle. Store the city where you found the cycle in a variable then start exploring again from the first city till you get to the city where the cycle was found (maybe this could be avoided) and store the number of steps taken. Now reduce these many steps from K. Then find the number of edges in the cycle and reduce K to K mod (edges in cycle). Now simply simulate the process for the [K mod (edges in cycle)] steps and you can find the city you’ll end at.
Using this approach I got an AC in 47 out of 55 test cases. Out of the 8 remaining I got TLE in 3 and WA in 5.
Here’s the code that I used:-
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(int i=a; i<b; i++)
#define ll long long
int main()
{
FASTIO
int n;
ll k;
cin >> n >> k;
vector<int> v(n);
rep(i,0,n)
{
cin >> v[i];
v[i]--;
}
set<int> nodes;
int pos = 0;
nodes.insert(pos);
int n_c = 0;
while(true)
{
if(nodes.find(v[pos]) == nodes.end())
{
nodes.insert(v[pos]);
pos = v[pos];
}
else
{
n_c = v[pos];
break;
}
}
pos = 0;
int steps = 0, cycle = 0;
while(pos != n_c)
{
steps++;
pos = v[pos];
}
pos = v[pos];
cycle++;
while(pos != n_c)
{
pos = v[pos];
cycle++;
}
k -= steps;
pos = n_c;
k %= cycle;
while(k--)
{
pos = v[pos];
}
cout << pos + 1 << "\n";
return 0;
}
Now here’s the question. Can I get an AC in the remaining test cases with some simple modifications to the above code?
