提出 #54770056

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll, ll>;
constexpr ll INF = 1e9 + 7;
constexpr ll mod = 1e9 + 7;
constexpr ld eps = 1e-9;
const ld PI = acos(-1);

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> g(n);
    for (ll i = 0; i < m; ++i) {
        ll u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    ll res = 0;
    vector<char> used(n, 0);
    for (ll v = 0; v < n; ++v) {
        if (used[v])continue;
        ll e = 0, c = 0;
        auto dfs = [&](auto &&dfs, int v) -> void {
            used[v] = 1;
            e += g[v].size();
            ++c;
            for (auto to: g[v]) {
                if (used[to])continue;
                dfs(dfs, to);
            }
        };
        dfs(dfs, v);
        e /= 2;
        res += c * (c - 1 )/2 - e;
    }
    cout << res;
    return 0;
}

提出情報

提出日時
問題 D - New Friends
ユーザ ZergTricky
言語 C++ 20 (gcc 12.2)
得点 350
コード長 1035 Byte
結果 AC
実行時間 160 ms
メモリ 18156 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 350 / 350
結果
AC × 3
AC × 36
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, sample_01.txt, sample_02.txt, sample_03.txt
ケース名 結果 実行時間 メモリ
random_01.txt AC 136 ms 15900 KiB
random_02.txt AC 115 ms 12424 KiB
random_03.txt AC 89 ms 13020 KiB
random_04.txt AC 85 ms 12012 KiB
random_05.txt AC 141 ms 15976 KiB
random_06.txt AC 119 ms 13040 KiB
random_07.txt AC 58 ms 11780 KiB
random_08.txt AC 36 ms 9844 KiB
random_09.txt AC 21 ms 8692 KiB
random_10.txt AC 13 ms 5508 KiB
random_11.txt AC 8 ms 4556 KiB
random_12.txt AC 3 ms 3648 KiB
random_13.txt AC 21 ms 8616 KiB
random_14.txt AC 9 ms 5040 KiB
random_15.txt AC 3 ms 3844 KiB
random_16.txt AC 7 ms 4488 KiB
random_17.txt AC 22 ms 8416 KiB
random_18.txt AC 2 ms 3572 KiB
random_19.txt AC 115 ms 14260 KiB
random_20.txt AC 29 ms 7324 KiB
random_21.txt AC 115 ms 14220 KiB
random_22.txt AC 63 ms 10564 KiB
random_23.txt AC 77 ms 15712 KiB
random_24.txt AC 78 ms 15700 KiB
random_25.txt AC 160 ms 17552 KiB
random_26.txt AC 43 ms 8188 KiB
random_27.txt AC 38 ms 18156 KiB
random_28.txt AC 6 ms 8040 KiB
random_29.txt AC 4 ms 6600 KiB
random_30.txt AC 1 ms 3408 KiB
random_31.txt AC 2 ms 3352 KiB
random_32.txt AC 2 ms 3412 KiB
random_33.txt AC 1 ms 3472 KiB
sample_01.txt AC 2 ms 3416 KiB
sample_02.txt AC 2 ms 3412 KiB
sample_03.txt AC 2 ms 3532 KiB