编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#6129 #1014. 波奇农场 Accepted 100 125 ms 12948 K C++ 17 / 1.6 K new_user_4 2023-10-12 21:31:13
显示原始代码
#include <bits/stdc++.h>

#define int long long

#define endl '\n'

#define ULL unsigned long long

#define rep(i, l, b) for (int i = l; i <= b; i++)

#define lep(i, b, l) for (int i = b; i >= l; i--)


const int N = 2e5 + 10, INF = 0x3f3f3f3f3f3f, MOD = 1e7 + 7, B = 13331;

using namespace std;

int n, m;
int a[N], b[N];
map<int, int> mp;

struct DSU {
    int n;
    vector<int> fa, sz;
    DSU(int n) : n(n) { init(n); }
    void init(int n) {
        fa.resize(n + 1), sz.resize(n + 1);
        for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
    }
    int find(int x) {
        while (x != fa[x]) x = fa[x];
        return x;
    }
    bool same(int u, int v) { return find(u) == find(v); }
    void merge(int u, int v) {
        int x = find(u);
        int y = find(v);
        if (x == y)
            return;
        if (sz[x] < sz[y])
            std::swap(x, y);
        sz[x] = sz[x] + sz[y];
        fa[y] = x;
    }
    int size(int x) { return sz[find(x)]; };
};

void solve() {
    mp.clear();
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n) cin >> b[i];

    DSU dsu(n);
    rep(i, 1, n) { dsu.merge(a[i], b[i]); }
    int ans = 0;
    rep(i, 1, n) {
        int idx = dsu.find(i);
        if (!mp[idx]) {
            mp[idx] = 1;
            ans += dsu.size(idx) - 1;
        }
    }
    cout << ans * 2 << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }

    return 0;
}
子任务 #1
Accepted
得分:100
测试点 #1
Accepted
得分:100
用时:4 ms
内存:344 KiB

输入文件(1.in

5
2 4 1 5 3
3 1 2 4 5

答案文件(1.out

8

用户输出

8

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:6 ms
内存:704 KiB

输入文件(2.in

10000
8410 2851 4799 7461 2256 1672 1961 330 2341 7908 7122 4283 4603 3214 520 2 6385 2691 137 1795
<97695 bytes omitted>

答案文件(2.out

19974

用户输出

19974

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:115 ms
内存:12948 KiB

输入文件(3.in

199999
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
<2577686 bytes omitted>

答案文件(3.out

199998

用户输出

199998

系统信息

Exited with return code 0