1263F - Economic Difficulties - CodeForces Solution

#include <bits/stdc++.h>

#define ll long long
using namespace std;

const int N = 2005;
const int M = 15;

vector<int> adj[N][2];

int device[N][2];

int depth[N][2],anc[N][M][2];

//test

void dfs(int node,int par,int parity) {

    anc[node][0][parity] = par;
    for(int i=1;i<M;++i) {
        anc[node][i][parity] = anc[anc[node][i-1][parity]][i-1][parity];
    }

    for(int ch : adj[node][parity]) {
        if(ch!=par) {
            depth[ch][parity] = depth[node][parity] + 1;
            dfs(ch,node,parity);
        }
    }
}

pair<int,int> getAnc(int x,int y,int parity) {
    int ret = 0;
    if(depth[x][parity]<depth[y][parity]) {
        swap(x,y);
    }
    ret = depth[x][parity] - depth[y][parity];
    for(int i=0;i<M;++i) {
        if(ret&(1<<i)) {
            x = anc[x][i][parity];
        }
    }
    if(x!=y) {
        for(int i=M-1;i>=0;--i) {
            if(anc[x][i][parity]!=anc[y][i][parity]) {
                ret += 2*(1<<i);
                x = anc[x][i][parity];
                y = anc[y][i][parity];
            }
        }
        ret += 2;
        x = anc[x][0][parity];
        y = anc[y][0][parity];
    }
    assert(x==y);
    return {x,ret};
}

int preSet[N][N][2];
int dp[N][N][2][2];



int solveDp(int cur,int last,int up,int iter,int n) {
    if(cur>n) {
        return 0;
    }
    int &ret = dp[cur][last][up][iter];
    if(ret!=-1) {
        return ret;
    }
    ret = 1e9;

    if(iter) {
        ret = min(ret, solveDp(cur+1,last,up,iter,n) + preSet[cur-1][cur][up]);
        ret = min(ret, solveDp(cur+1,cur-1,up^1,1,n) + preSet[last][cur][up^1]);
    } else {
        assert(0);
    }
    return ret;
}

void solve2() {
    int n,a,b;
    scanf("%d ",&n);

    scanf("%d ",&a);
    for(int i=2;i<=a;++i) {
        int p;
        scanf("%d ",&p);
        adj[p][0].push_back(i);
    }
    for(int i=1;i<=n;++i) {
        scanf("%d ",&device[i][0]);
    }

    scanf("%d ",&b);

    for(int i=2;i<=b;++i) {
        int p;
        scanf("%d ",&p);
        adj[p][1].push_back(i);
    }
    for(int i=1;i<=n;++i) {
        scanf("%d ",&device[i][1]);
    }
    device[0][0] = device[0][1] = 1;
    dfs(1,0,0);
    dfs(1,0,1);

    for(int up=0;up<2;++up) {
        for(int i=0;i<=n;++i) {
            for(int j=0;j<=n;++j) {
                int lca = getAnc(device[i][up], device[j][up],up).first;
                preSet[i][j][up] = depth[device[j][up]][up] - depth[lca][up];
            }
        }
    }
    memset(dp,-1,sizeof(dp));
    printf("%d\n", a+b-2 - min(solveDp(1,0,1,1,n), solveDp(1,0,0,1,n)));
}

void solve() {
    // init();
    // int t;
    // scanf("%d",&t);
    // while(t--)
    solve2();
}

inline bool exists_test0 (const std::string& name);
inline bool exists_test1 (const std::string& name);
int main() {
  solve();
  return 0;
}

/*
0. Enough array nsize? Enough array nsize? Integer overflow?

1. Think TWICE, Code ONCE!
Are there any counterexamples to your algo?

2. Be careful about the BOUNDARIES!
N=1? P=1? Something about 0?

3. Do not make STUPID MISTAKES!
Time complexity? Memory usage? Precision error?

4. Be careful to use wrong variable.
*/
inline bool exists_test0 (const std::string& name) {
    ifstream f(name.c_str());
    return f.good();
}

inline bool exists_test1 (const std::string& name) {
    if (FILE *file = fopen(name.c_str(), "r")) {
        fclose(file);
        return true;
    } else {
        return false;
    }
}