Submission #488682

#TimeUsernameProblemLanguageResultExecution timeMemory
488682SirCovidThe19thSpecial graph (IZhO13_specialg)C++17
0 / 100
7 ms2776 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, x, y) for (int i = x; i < y; i++) const int mx = 1e5 + 5; int n, q, to[mx], dep[mx], tin[mx], tout[mx], ti, cyc[mx]; bool vis[mx], active[mx]; vector<int> startDFS, adj[mx]; template<int sz> struct segTreeRP{ int seg[sz * 2]; int comb(int a, int b){ return tin[a] > tin[b] ? a : b; //we want lower node so greatest tin val } void upd(int l, int r, int v){ for (l += sz, r += sz; l <= r; r /= 2, l /= 2){ if (l % 2 == 1) seg[l] = comb(seg[l], v), l++; if (r % 2 == 0) seg[r] = comb(seg[r], v), r--; } } int qry(int i){ int ret = 0; for (i += sz; i; i /= 2) ret = comb(ret, seg[i]); return ret; } };segTreeRP<mx> st; void findStartPts(int cur){ active[cur] = vis[cur] = 1; int nxt = to[cur]; if (!nxt) startDFS.push_back(cur); //endpoint of chain else{ if (!vis[nxt]) findStartPts(nxt); else if (active[nxt]) startDFS.push_back(cur); //part of cycle } active[cur] = 0; } bool isAnc(int A, int B){ return tin[A] <= tin[B] and tout[A] >= tout[B]; } void dfs(int cur){ tin[cur] = ++ti; for (int nxt : adj[cur]){ if (!tin[nxt]) dep[nxt] = dep[cur] + 1, dfs(nxt); else cyc[nxt] = cur; } tout[cur] = ti; } void rem(int X){ //remove edge outgoing from X if (cyc[X]) cyc[X] = 0; else st.upd(tin[X], tout[X], X); } int solve(int A, int B){ //A goes to B int ret = 0, root = st.qry(tin[A]); if (!isAnc(B, A)){ //go to root and use cycle ret += dep[A] - dep[root] + 1; A = cyc[root]; } if (isAnc(B, A) and tin[B] >= tin[root]) ret += dep[A] - dep[B]; else ret = -1; return ret <= 0 ? -1 : ret; } int main(){ cin >> n; FOR(i, 1, n + 1){ cin >> to[i]; if (to[i]) adj[to[i]].push_back(i); } FOR(i, 1, n + 1) if (!vis[i]) findStartPts(i); for (int i : startDFS){ dfs(i); st.upd(tin[i], tout[i], i); } cin >> q; while (q--){ int tp, A, B; cin >> tp; if (tp == 1) cin >> A, rem(A); else cin >> A >> B, cout<<solve(A, B)<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...