oj.uz

답안 #946378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
946378 2024-03-14T14:58:14 Z Berted 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 2 ms 10844 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define fst first
#define snd second

using namespace std;

const int IN = 0, OUT = 1;

int N, M;
int rep[100001][2], par[100001]; // 0 -> in; 1 -> out
ll sz[100001];             
set<int> deg[100001][2];
ll sum = 0;

queue<pii> Q;

int find(int x) {return par[x] = (par[x] == x) ? x : find(par[x]);}
void join(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    sum -= sz[a] * sz[a];
    sum -= sz[b] * sz[b];
    
    sz[a] += sz[b];
    par[b] = a;
    
    sum += sz[a] * sz[a];
    
    int Ain = rep[a][IN], Bin = rep[b][IN];
    sum -= deg[Ain][IN].size() * sz[a];
    sum -= deg[Bin][IN].size() * sz[b];
    if (deg[Ain][IN].size() < deg[Bin][IN].size()) swap(Ain, Bin);
    for (const auto &x : deg[Bin][IN]) {
        deg[Ain][IN].insert(x);
        deg[x][OUT].erase(Bin);
        deg[x][OUT].insert(Ain);
    }
    deg[Bin][IN].clear();
    sum += deg[Ain][IN].size() * sz[a];
    rep[a][IN] = Ain;

    int Aout = rep[a][OUT], Bout = rep[b][OUT];
    if (deg[Aout][OUT].size() < deg[Bout][OUT].size()) swap(Aout, Bout);
    for (const auto &x : deg[Bout][OUT]) {
        deg[Aout][OUT].insert(x);
        deg[x][IN].erase(Bout);
        deg[x][IN].insert(Aout);
        if (deg[rep[find(x)][OUT]][OUT].count(Ain)) Q.push({a, find(x)});
    }
    deg[Bout][OUT].clear();
    rep[a][OUT] = Aout;

    //cerr << a << " join " << b << " " << sum << "\n";
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        rep[i][IN] = rep[i][OUT] = i;
        par[i] = i;
        sz[i] = 1;
    }

    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v; u--; v--;

        int ruo = rep[find(u)][OUT], rui = rep[find(u)][IN];
        int rvo = rep[find(v)][OUT], rvi = rep[find(v)][IN];
        if (deg[ruo][OUT].count(rvi) == 0) sum++;
        deg[ruo][OUT].insert(rvi);
        deg[rvi][IN].insert(ruo);
        
        if (deg[rui][IN].count(rvo)) {
            Q.push({find(u), find(v)});
        }
        
        while (Q.size()) {
            auto [a, b] = Q.front(); Q.pop();
            a = find(a), b = find(b);
            sum -= 2;
            deg[rep[a][IN]][IN].erase(rep[b][OUT]);
            deg[rep[b][IN]][IN].erase(rep[a][OUT]);
            deg[rep[a][OUT]][OUT].erase(rep[b][IN]);
            deg[rep[b][OUT]][OUT].erase(rep[a][IN]);
            join(a, b);
        }

        cout << sum << "\n";
    }
    return 0;
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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