# Planet cycles timeout

I’m timing out on planet cycles, which is quite peculiar since I’m passing other 2e5 solutions with a fairly large margin (0.07 seconds). My approach is first to get rid of all the cycles using floyd’s cycle finding algorithm, and then to run dfs to get the shortest distance to such a cycle, but it TLEs on 3 test cases.

``````#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python!

#pragma GCC optimize("O3")
#pragma GCC optimization ("unroll-loops")

using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;

// pairs
#define mp make_pair
#define f first
#define s second

// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
#define rtn return

#define lb lower_bound
#define ub upper_bound
tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }

// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define each(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const db PI = acos((db)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
const char nl = '\n';
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;

// bitwise ops
// also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int bits(int x) { // assert(x >= 0); // make C++11 compatible until USACO updates ...
return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x))
constexpr int p2(int x) { return 1<<x; }
constexpr int msk2(int x) { return p2(x)-1; }

ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down

tcT> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; }

tcTU> T fstTrue(T lo, T hi, U f) {
hi ++; assert(lo <= hi); // assuming f is increasing
while (lo < hi) { // find first index such that f is true
T mid = lo+(hi-lo)/2;
f(mid) ? hi = mid : lo = mid+1;
}
return lo;
}
tcTU> T lstTrue(T lo, T hi, U f) {
lo --; assert(lo <= hi); // assuming f is decreasing
while (lo < hi) { // find first index such that f is true
T mid = lo+(hi-lo+1)/2;
f(mid) ? lo = mid : hi = mid-1;
}
return lo;
}
tcT> void remDup(vector<T>& v) { // sort and remove duplicates
sort(all(v)); v.erase(unique(all(v)),end(v)); }
tcTU> void erase(T& t, const U& u) { // don't erase
auto it = t.find(u); assert(it != end(t));
t.erase(it); } // element that doesn't exist from (multi)set

// INPUT
#define tcTUU tcT, class ...U
tcT> void re(complex<T>& c);
tcTU> void re(pair<T,U>& p);
tcT> void re(V<T>& v);
tcT, size_t SZ> void re(AR<T,SZ>& a);

tcT> void re(T& x) { cin >> x; }
void re(double& d) { str t; re(t); d = stod(t); }
void re(long double& d) { str t; re(t); d = stold(t); }
tcTUU> void re(T& t, U&... u) { re(t); re(u...); }

tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; }
tcTU> void re(pair<T,U>& p) { re(p.f,p.s); }
tcT> void re(V<T>& x) { each(a,x) re(a); }
tcT, size_t SZ> void re(AR<T,SZ>& x) { each(a,x) re(a); }
tcT> void rv(int n, V<T>& x) { x.rsz(n); re(x); }

// DECLARATION AND INPUT
#define revi(x, n) vi x(n); re(x)
#define revp(x, n) vpi x(n); re(x);
#define revd(x, n) vd x(n); re(x);
#define rei(x, n) int x; re(x);
#define redb(x, n) db x; re(x);

// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) {
// #ifdef LOCAL
// 	return b ? "true" : "false";
// #else
return ts((int)b);
// #endif
}
tcT> str ts(complex<T> c) {
stringstream ss; ss << c; return ss.str(); }
str ts(V<bool> v) {
str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
str res = ""; F0R(i,SZ) res += char('0'+b[i]);
return res; }
tcTU> str ts(pair<T,U> p);
tcT> str ts(T v) { // containers with begin(), end()
#ifdef LOCAL
bool fst = 1; str res = "{";
for (const auto& x: v) {
if (!fst) res += ", ";
fst = 0; res += ts(x);
}
res += "}"; return res;
#else
bool fst = 1; str res = "";
for (const auto& x: v) {
if (!fst) res += " ";
fst = 0; res += ts(x);
}
return res;

#endif
}
tcTU> str ts(pair<T,U> p) {
#ifdef LOCAL
return "("+ts(p.f)+", "+ts(p.s)+")";
#else
return ts(p.f)+" "+ts(p.s);
#endif
}

// OUTPUT
tcT> void pr(T x) { cout << ts(x); }
tcTUU> void pr(const T& t, const U&... u) {
pr(t); pr(u...); }
void ps() { pr("\
"); } // print w/ spaces
tcTUU> void ps(const T& t, const U&... u) {
pr(t); if (sizeof...(u)) pr(" "); ps(u...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
tcTUU> void DBG(const T& t, const U&... u) {
cerr << ts(t); if (sizeof...(u)) cerr << ", ";
DBG(u...); }
#ifdef LOCAL // compile with -DLOCAL, chk -> fake assert
#define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \\
<< __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\
", exit(0);
#else
#define dbg(...) 0
#define chk(...) 0
#endif

void setPrec() { cout << fixed << setprecision(15); }
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
// FILE I/O
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }
void setIO(str s = "") {
unsyncIO(); setPrec();
// cin.exceptions(cin.failbit);
// throws exception when do smth illegal
// ex. try to read letter into int
if (sz(s)) setIn(s+".in"), setOut(s+".out"); // for USACO
}

int N;
int P[MX];
int dist[MX];
int vis[MX];

vi cycle;

// void dfs(int x) {
// 	dbg(cycle);
// 	if(vis[x] || dist[x] != MOD) return;
// 	if(sz(cycle) && cycle[0] == x) {
// 		each(a, cycle) {
// 			vis[a] = true;
// 			dist[a] = sz(cycle);
// 		}
// 		cycle = vi();
// 	} else {
// 		cycle.pb(x);
// 		if(dist[P[x]] == MOD) dfs(P[x]);
// 		else dist[x] = 1 + dist[P[x]], vis[x] = true;
// 	}
// }

void dfs(int x) { // gets rid of all cycles
int a = P[x], b = P[P[x]];
while(a != b) {
a = P[a];
b = P[P[b]];
}

a = x;
while(a != b) {
a = P[a];
b = P[b];
}

b = P[a];
stack<int> cycle;
cycle.push(a);
cycle.push(b);
int l = 1;
while(a != b) {
b = P[b];
cycle.push(b);
l++;
}

while(sz(cycle)) {
int x = cycle.top();
dist[x] = l;
cycle.pop();
}
}

int dfs2(int x, int d) {
if(dist[P[x]] != MOD) return dist[x] = dist[P[x]] + 1;
else {
return dist[x] = dfs2(P[x], d + 1) + 1;
}
}

int main() {
clock_t start = clock();
setIO("planetcycles");

re(N);
F0R(i, N) re(P[i]);
F0R(i, N) --P[i];
F0R(i, N) dist[i] = MOD;

F0R(i, N) if(dist[i] == MOD) dfs(i); // initial dfs => gets rid of all cycles
F0R(i, N) if(dist[i] == MOD) dfs2(i, 1); // shortest distance to nearest cycle

// F0R(i, N) pr(dist[i], i == N-1 ? "" : " ");
F0R(i, N-1) {
pr(dist[i], " ");
}

pr(dist[N-1], nl);

cerr << "Total Time: " << (double)(clock() - start)/ CLOCKS_PER_SEC;
// you should actually read the stuff at the bottom
}

/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
``````

can you please just remove the macros lol it makes the code nearly unreadablle

1 Like

Try downloading the test data and running locally to determine if your code is too slow (it finishes running after a while) or if it’s a bug (it never finished running).

1 Like

what a plug

since there is no solution for this on usaco guide I’m also curious what the idea behind solving Planet Cycles is. I’m getting time out for many cases not sure if it’s because of infinite loop during flyod algorithm

A solution has just been added. Let me know if the explanation is confusing or if there’s anything that doesn’t make sense.

Wow I didn’t expect such a quick response. Thank you very much, I’ll check it out later!