oj.uz

Submission #488689

# Submission time Handle Problem Language Result Execution time Memory
488689 2021-11-20T05:13:29 Z SirCovidThe19th Special graph (IZhO13_specialg) C++17
100 / 100
 229 ms 14660 KB 
#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 dep[a] > dep[b] ? a : b; //we want lower node so the one with greater dep
    }
    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]; root = st.qry(tin[A]); //we can be in a "new" tree so lets upd root
    }
    if (isAnc(B, A) and tin[B] >= tin[root]) ret += dep[A] - dep[B];
    else ret = -1;

    return 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){
        dep[i] = 1; 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";
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2764 KB Output is correct
2 Correct 7 ms 2764 KB Output is correct
3 Correct 9 ms 2796 KB Output is correct
4 Correct 17 ms 2780 KB Output is correct
5 Correct 8 ms 2764 KB Output is correct
6 Correct 38 ms 2800 KB Output is correct
7 Correct 38 ms 2844 KB Output is correct
8 Correct 38 ms 2764 KB Output is correct
9 Correct 38 ms 2764 KB Output is correct
10 Correct 38 ms 2892 KB Output is correct
11 Correct 228 ms 14332 KB Output is correct
12 Correct 208 ms 8284 KB Output is correct
13 Correct 215 ms 10160 KB Output is correct
14 Correct 203 ms 7584 KB Output is correct
15 Correct 213 ms 8540 KB Output is correct
16 Correct 205 ms 8360 KB Output is correct
17 Correct 224 ms 12096 KB Output is correct
18 Correct 229 ms 12012 KB Output is correct
19 Correct 224 ms 11996 KB Output is correct
20 Correct 224 ms 14660 KB Output is correct