Submission #156090

#	Time	Username	Problem	Language	Result	Execution time	Memory
156090		atoiz	우호 조약 체결 (JOI14_friends)	C++14	100 / 100	163 ms	12664 KiB

friends

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100007;

int n, m;
vector<int> gr[MAXN];
bool vis[MAXN];

int dsu[MAXN], sz[MAXN];
void init(int n) { for (int i = 0; i < n; ++i) dsu[i] = i, sz[i] = 1; }
int get(int i) { return (i == dsu[i] ? i : dsu[i] = get(dsu[i])); }
bool same(int i, int j) { return get(i) == get(j); }
void join(int i, int j) { i = get(i), j = get(j); if (i == j) return; if (sz[i] < sz[j]) swap(i, j); sz[i] += sz[j], dsu[j] = i; }

void dfs(int);
void add(int u, int v)
{
    bool redfs = (!vis[v] || sz[get(v)] == 1);
    // cerr << "S " << u << ' ' << v << ' ' << redfs << endl;
    join(u, v);
    if (redfs) dfs(v);
}
void dfs(int u)
{
    // cerr << u << ": " << sz[get(u)] << endl;
    vis[u] = 1;
    if (sz[get(u)] > 1) for (int v : gr[u]) add(u, v);
    else if ((int) gr[u].size() == 1) {
        if (!vis[gr[u][0]]) dfs(gr[u][0]);
    } else if ((int) gr[u].size() > 1) {
        bool redfs = sz[gr[u].back()] == 1;
        add(gr[u].back(), gr[u].front());
        for (int v : gr[u]) if (v != gr[u].front()) add(gr[u].front(), v);
        if (redfs) dfs(gr[u].back());
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        gr[u].push_back(v);
    }
    init(n + 1);
    for (int u = 1; u <= n; ++u) if (!vis[u]) dfs(u);

    long long ans = 0;
    for (int u = 1; u <= n; ++u) for (int v : gr[u]) {
        if (!same(u, v)) ++ans;
    }
    for (int u = 1; u <= n; ++u) if (u == get(u)) ans += 1ll * sz[u] * (sz[u] - 1);
    cout << ans << endl;
}

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