40pts求调
查看原帖
40pts求调
362750
TernaryTree楼主2023/5/29 21:36
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e5 + 10;
const int maxv = 1e6 + 10;

struct edge { int to, next, w; };

int n, ans;
int a[maxn];
int b[maxn];
vector<int> p[maxv];
int head[maxn];
edge e[maxn << 2];
int cnt;

void add_edge(int u, int v, int w) {
    e[++cnt] = {v, head[u], w};
    head[u] = cnt;
}

int vis[maxn];
int c[2];

void dfs(int u, int f) {
    ++c[f];
    vis[u] = true;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to, w = e[i].w;
        if (!vis[v]) dfs(v, f ^ w);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) if (a[i] != b[i]) p[a[i]].push_back(i), p[b[i]].push_back(i);
    for (int i = 1; i < maxv; i++) {
        if (p[i].size() == 2) {
            int u = p[i][0], v = p[i][1], f = (a[u] == b[v] || a[v] == b[u]);
            add_edge(u, v, f), add_edge(v, u, f);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            c[0] = c[1] = 0;
            dfs(i, 0);
            ans += min(c[0], c[1]);
        }
    }
    cout << ans << endl;
    return 0;
}

2023/5/29 21:36
加载中...