oj.uz

답안 #359330

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
359330 2021-01-26T19:23:06 Z valerikk 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 7 ms 9708 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e5 + 7;

int n, m;
int p[N];
int sz[N];
set<int> in[N], out[N];

int par(int v) {
    return p[v] == v ? v : p[v] = par(p[v]);
}

bool unite(int a, int b) {
    a = par(a);
    b = par(b);
    if (a == b || !out[a].count(b) || !out[b].count(a)) return false;
    if (sz[a] > sz[b]) swap(a, b);
    sz[b] += sz[a];
    out[a].erase(b);
    out[b].erase(a);
    in[a].erase(b);
    in[b].erase(a);
    p[a] = b;
    vector<pair<int, int>> to;
    for (int v : out[a]) {
        in[v].erase(a);
        in[v].insert(b);
        if (in[b].count(v)) to.push_back({b, v});
        out[b].insert(v);
    }
    out[a].clear();
    for (int v : in[a]) {
        out[v].erase(a);
        out[v].insert(b);
        if (out[b].count(v)) to.push_back({b, v});
        in[b].insert(v);
    }
    in[a].clear();
    for (auto t : to) unite(t.first, t.second);
    return true;
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        p[i] = i, sz[i] = 1;
    while (m--) {
        int a, b;
        cin >> a >> b;
        a = par(a);
        b = par(b);
        if (a != b) {
            out[a].insert(b);
            in[b].insert(a);
            unite(a, b);
        }
        ll sum = 0;
        for (int i = 1; i <= n; i++) {
            if (p[i] == i) {
                sum += (ll)sz[i] * (sz[i] - 1);
                for (int v : out[i]) sum += (ll)sz[i] * sz[v];
            }
        }
        cout << sum << "\n";
    }
    return 0;
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9708 KB Output isn't correct
2 Halted 0 ms 0 KB -