Submission #1070264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070264		juicy	우호 조약 체결 (JOI14_friends)	C++17	100 / 100	58 ms	13008 KiB

friends

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5;

int n, m;
int pr[N];
bool vis[N];
vector<int> g[N];

int find(int u) {
    return pr[u] < 0 ? u : pr[u] = find(pr[u]);
}

void mrg(int u, int v) {
    if ((u = find(u)) == (v = find(v))) {
        return;
    }
    if (pr[u] > pr[v]) {
        swap(u, v);
    }
    pr[u] += pr[v];
    pr[v] = u;
} 

void dfs(int u, int root) {
    vis[u] = 1;
    for (int v : g[u]) {
        mrg(v, root);
        if (!vis[v]) {
            dfs(v, root);
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n >> m;
    vector<array<int, 2>> edges;
    while (m--) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        edges.push_back({u, v});
    }
    fill(pr + 1, pr + n + 1, -1);
    for (int i = 1; i <= n; ++i) {
        if (g[i].size() > 1) {
            int root = g[i][0];
            for (int v : g[i]) {
                mrg(v, root);
                if (!vis[v]) {
                    dfs(v, root);
                }
            }
        }
    }
    long long res = 0;
    for (auto [u, v] : edges) {
        res += find(u) != find(v);
    }
    for (int i = 1; i <= n; ++i) {
        if (pr[i] < 0) {
            res += (long long) -pr[i] * (-pr[i] - 1);
        }
    }
    cout << res;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65