/**
Problem: Special graph
Source: IX Zhautykov Olympiad on Mathematics, Physics and Informatics (IZhO) 2013
*/
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
struct TQuery {int x, y, tme;};
const int N = 1e5+2;
const int LN = 17;
const int INF = 1e9;
int n, q, ncyc, nextv[N], exp[N], tme, num[N], low[N], p[LN][N], f[LN][N], cycid[N], cycpos[N], h[N], din[N];
int pw2[N];
vector<int> g[N], scc[N];
stack<int> st;
TQuery r[N];
void Prep()
{
for (int i = 1; i < N; i <<= 1) pw2[i] = i;
for (int i = N - 1; i >= 0; --i)
if (!pw2[i]) pw2[i] = pw2[i + 1];
}
class TTree
{
vector<int> it;
public:
void Update(int id, int sl, int sr, int u, int v)
{
if (sl == sr)
{
it[id] = v;
return;
}
int mid = (sl + sr) / 2;
if (u <= mid) Update(id*2+1, sl, mid, u, v);
else Update(id*2+2, mid+1, sr, u, v);
it[id] = min(it[id*2+1], it[id*2+2]);
}
int Query(int id, int sl, int sr, int ql, int qr)
{
if (sl > qr || sr < ql || ql > qr) return INF;
if (ql <= sl && sr <= qr) return it[id];
int mid = (sl + sr) / 2;
return min(Query(id*2+1, sl, mid, ql, qr), Query(id*2+2, mid+1, sr, ql, qr));
}
void Init(int n) {it = vector<int>(pw2[n] << 1, INF);}
} tree[N];
void Dfs1(int u)
{
num[u] = low[u] = ++tme;
st.push(u);
if (nextv[u])
{
int v = nextv[u];
if (!num[v]) Dfs1(v), low[u] = min(low[u], low[v]);
else low[u] = min(low[u], num[v]);
}
if (low[u] == num[u])
{
++ncyc;
int x;
do
{
x = st.top(); st.pop();
scc[ncyc].push_back(x);
low[x] = num[x] = INF;
} while (x != u);
for (size_t i = 0; i < scc[ncyc].size(); ++i)
{
int v = scc[ncyc][i];
cycid[v] = ncyc;
cycpos[v] = i;
}
if (scc[ncyc].size() > 1U)
{
int n = scc[ncyc].size();
tree[ncyc].Init(n);
for (int i = 0; i < n; ++i)
{
int v = scc[ncyc][i];
tree[ncyc].Update(0, 0, n-1, i, exp[v]);
}
}
else f[0][ncyc] = exp[u];
}
}
void Dfs2(int u)
{
num[u] = 1;
for (int v: g[u])
{
h[v] = h[u] + 1;
p[0][v] = u;
Dfs2(v);
}
}
void BuildLCA()
{
for (int j = 1; j < LN; ++j)
for (int i = 1; i <= ncyc; ++i)
{
p[j][i] = p[j-1][p[j-1][i]];
f[j][i] = min(f[j-1][i], f[j-1][p[j-1][i]]);
}
}
int KthParent(int u, int k, int tme)
{
int low = INF;
for (int i = LN-1; i >= 0; --i)
if (k - (1 << i) >= 0)
{
low = min(low, f[i][u]);
u = p[i][u];
k -= 1 << i;
}
if (low < tme) return -1;
return u;
}
int QueryCycle(int cyc, int x, int y, int tme) // x -> y
{
int n = scc[cyc].size();
if (x < y)
{
return min(tree[cyc].Query(0, 0, n-1, 0, x), tree[cyc].Query(0, 0, n-1, y+1, n-1)) > tme ? n - (y - x) : -1;
}
else return tree[cyc].Query(0, 0, n-1, y+1, x) > tme ? x - y : -1;
}
int Query(int x, int y, int tme) // x -> y
{
if (x == y) return 0;
if (cycid[x] == cycid[y])
{
int cyc = cycid[x];
x = cycpos[x], y = cycpos[y];
return QueryCycle(cyc, x, y, tme);
}
else // x and y do not belong to the same cycle
{
int u = cycid[x], v = cycid[y];
if (h[v] > h[u]) return -1;
int re = h[u] - h[v];
if (KthParent(u, h[u] - h[v], tme) != v) return -1;
if (scc[v].size() > 1) // v is a cycle
{
int val = QueryCycle(v, cycpos[nextv[scc[KthParent(u, h[u] - h[v] - 1, tme)][0]]], cycpos[y], tme);
return val == -1 ? -1 : re + val;
}
else return re;
}
}
void Solve()
{
for (int i = 1; i <= n; ++i)
if (!num[i]) Dfs1(i);
for (int i = 1; i <= n; ++i)
if (nextv[i] && cycid[nextv[i]] != cycid[i])
{
g[cycid[nextv[i]]].push_back(cycid[i]);
++din[cycid[i]];
}
fill(num+1, num+1+ncyc, 0);
for (int i = 1; i <= ncyc; ++i)
if (!din[i] && !num[i]) Dfs2(i); // start of chains
for (int i = 1; i <= ncyc; ++i)
if (!num[i]) Dfs2(i); // only cycles left
BuildLCA();
for (int i = 0; i < q; ++i)
{
int x = r[i].x, y = r[i].y, tme = r[i].tme;
printf("%d\n",Query(x, y, tme));
}
}
int main()
{
Prep();
scanf("%d",&n);
for (int i = 1; i <= n; ++i) scanf("%d",&nextv[i]);
int queries;
scanf("%d",&queries);
fill(exp+1, exp+1+n, INF);
for (int i = 1, type, x, y; i <= queries; ++i)
{
scanf("%d",&type);
if (type == 1)
{
scanf("%d",&x); exp[x] = i;
}
else
{
scanf("%d%d",&x,&y);
r[q++] = {x, y, i};
}
}
Solve();
return 0;
}
Compilation message
specialg.cpp: In function 'int main()':
specialg.cpp:194:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
specialg.cpp:195:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i <= n; ++i) scanf("%d",&nextv[i]);
~~~~~^~~~~~~~~~~~~~~~
specialg.cpp:197:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&queries);
~~~~~^~~~~~~~~~~~~~~
specialg.cpp:201:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&type);
~~~~~^~~~~~~~~~~~
specialg.cpp:204:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x); exp[x] = i;
~~~~~^~~~~~~~~
specialg.cpp:208:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
8312 KB |
Output is correct |
| 2 |
Correct |
10 ms |
8420 KB |
Output is correct |
| 3 |
Correct |
10 ms |
8476 KB |
Output is correct |
| 4 |
Correct |
12 ms |
8568 KB |
Output is correct |
| 5 |
Correct |
11 ms |
8596 KB |
Output is correct |
| 6 |
Correct |
21 ms |
9060 KB |
Output is correct |
| 7 |
Correct |
21 ms |
9124 KB |
Output is correct |
| 8 |
Correct |
21 ms |
9252 KB |
Output is correct |
| 9 |
Correct |
21 ms |
9252 KB |
Output is correct |
| 10 |
Correct |
22 ms |
9260 KB |
Output is correct |
| 11 |
Runtime error |
647 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
