Submission #58480

#	Time	Username	Problem	Language	Result	Execution time	Memory
58480		Benq	Special graph (IZhO13_specialg)	C++14	100 / 100	169 ms	41780 KiB

specialg

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;


template<int SZ> struct DSU {
    int par[SZ], sz[SZ];
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) return 0;
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], par[y] = x;
    	return 1;
    }
};

DSU<MX> D;
int N, M, nex[MX][17], bad[MX], depth[MX];
pi cyc[MX]; // #, pos
int cycsz[MX];
set<int> lef[MX];

vector<array<int,3>> q;
vi ret;

void addEdge(int x) {
    D.unite(x,nex[x][0]);
    if (cyc[x].f) lef[cyc[x].f].erase(cyc[x].s);
}

bool con(int t, int y) {
    assert(t != y);
    int co = cyc[t].f;
    t = cyc[t].s, y = cyc[y].s;
    auto it = lef[co].lb(t);
    if (t > y) {
        if (it != lef[co].end()) return 0;
        it = lef[co].begin();
    }
    return it == lef[co].end() || *it >= y;
}

int dis(int t, int y) {
    int cur = cyc[y].s-cyc[t].s;
    if (cur < 0) cur += cycsz[t];
    return cur;
}

int anc(int x, int d) {
    F0Rd(i,17) if (d&(1<<i)) x = nex[x][i];
    return x;
}

int query(int x, int y) {
    if (D.get(x) != D.get(y)) return -1;
    if (depth[x] >= depth[y]) {
        int t = anc(x,depth[x]-depth[y]);
        if (t == y) return depth[x]-depth[y];
    }
    if (depth[y]) return -1;
    int t = anc(x,depth[x]);
    if (con(t,y)) return depth[x]+dis(t,y);
    return -1;
}

int vis[MX];

void solve(int x) {
    int X = x;
    vi cur;
    while (1) {
        // cout << "AH " << x << " " << X << " " << vis[X] << "\n";
        if (X == 0) return;
        if (vis[X] == 0) {
            vis[X] = x;
        } else if (vis[X] == x) {
            vis[X] += N;
            cur.pb(X);
        } else if (vis[X] == x+N) {
            break;
        } else return;
        X = nex[X][0];
    }
    // cout << "OH " << x << " " << sz(cur) << " " << cur[0] << "\n";
    F0R(i,sz(cur)) {
        cyc[cur[i]] = {x,i};
        cycsz[cur[i]] = sz(cur);
        lef[x].insert(i);
    }
}

int getDepth(int x) {
    if (depth[x]) return depth[x];
    if (x == 0  || vis[x] > N) return 0;
    return depth[x] = getDepth(nex[x][0])+1;
}

void process() {
    // cyc, cycsz, lef
    FOR(i,1,N+1) solve(i);
    FOR(i,1,N+1) if (vis[i] <= N) {
        depth[i] = getDepth(i);
       // cout << "BLAH " << i << " " << depth[i] << "\n";
    }
    /*FOR(i,1,N+1) {
        cout << cyc[i].f << " " << cyc[i].s << " " << cycsz[i] << " " << depth[i] << "\n";
    }*/
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    FOR(i,1,N+1) {
        cin >> nex[i][0];
        if (nex[i][0] == i) nex[i][0] = 0;
    }
    FOR(i,1,17) FOR(j,1,N+1) nex[j][i] = nex[nex[j][i-1]][i-1];
    process();
    cin >> M;
    F0R(i,M) {
        int t; cin >> t;
        if (t == 1) {
            int a; cin >> a; bad[a] = 1;
            q.pb({1,a,0});
        } else {
            int a,b; cin >> a >> b; 
            q.pb({2,a,b});
        }
    }
    FOR(i,1,N+1) if (!bad[i] && nex[i][0]) addEdge(i);
    reverse(all(q));
    for (auto a: q) {
        if (a[0] == 1) addEdge(a[1]);
        else ret.pb(query(a[1],a[2]));
    }
    reverse(all(ret));
    for (int i: ret) cout << i << "\n";
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

• Subtask 1: 100 / 100