Submission #488685

#	Time	Username	Problem	Language	Result	Execution time	Memory
488685		SirCovidThe19th	Special graph (IZhO13_specialg)	C++17	100 / 100	250 ms	16480 KiB

specialg

#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 (A == B or !isAnc(B, A)){ //go to root and use cycle
        ret += dep[A] - dep[root] + 1;
        A = cyc[root]; root = st.qry(tin[A]);
    }
    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){
        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 / 100