Submission #43171

#	Time	Username	Problem	Language	Result	Execution time	Memory
43171		nickyrio	우호 조약 체결 (JOI14_friends)	C++14	100 / 100	151 ms	90684 KiB

friends

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define DEBUG(x) { cerr << #x << '=' << x << endl; }
#define Arr(a, l, r) { cerr << #a << " = {"; FOR(_, l, r) cerr << ' ' << a[_]; cerr << "}\n"; }
#define N 1001000
#define pp pair<int, int>
#define endl '\n'
#define IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define taskname ""
#define bit(S, i) (((S) >> (i)) & 1)
using namespace std;

int visited[N], f[N], n;
vector<int> e[N];

int root(int u) { return f[u] < 0 ? u : (f[u] = root(f[u])); }
void Union(int a, int b){
    a = root(a), b = root(b);
    if (a == b) return;
    int t = f[a] + f[b];
    if (f[a] > f[b]) swap(a, b);
    f[a] = t;
    f[b] = a;    
}

void dfs(int u) {
    visited[u] = 1;
    for (int v : e[u]) {
        Union(u, v);
        if (!visited[v]) dfs(v);
    }
}
int main() {
    #ifdef NERO
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    #endif //NERO
    IO;
    int m;
    cin >> n >> m;
    REP(i, m) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
    }
    FOR(u, 1, n) f[u] = -1;
    long long ans = 0;
    FOR(u, 1, n) if (!visited[u]) {
        if (e[u].size() > 1) {
            int r = -1;
            for (int v : e[u]) {
                if (r != -1) Union(r, v);
                else r = v;
                dfs(v);
            }
        }
       // DEBUG(cnt);
    }
    //Arr(f, 1, n);
    FOR(u, 1, n) if (f[u] < 0) ans += 1ll * f[u] * (f[u] + 1);
    FOR(u, 1, n) {
        for (int v : e[u]) if (root(u) != root(v)) ans++;
    }
    cout << ans;
}

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