oj.uz

답안 #1037347

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1037347 2024-07-28T14:25:38 Z Macker 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 0 ms 344 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long double ld;
typedef long long ll;
#define int ll
typedef pair<int, int> pii;

#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define inf LLONG_MAX/2
#define ff first
#define ss second
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
#define last(s) (*--s.end())
#define first(s) *s.begin()

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")

vector<int> par;
vector<set<int>> to, pfrom, comp;
int res = 0;
vector<pii> todo;

int find(int a){
    while(par[a] >= 0) a = par[a];
    return a;
}

void uni(int a, int b){
    a = find(a);
    b = find(b);
    if(-par[a] < -par[b]) swap(a, b);

    res -= (-par[a]) * ((-par[a]) - 1);
    res -= (-par[b]) * ((-par[b]) - 1);
    res -= to[a].size() * (-par[a]);
    res -= to[b].size() * (-par[b]);

    par[a] += par[b];
    for (auto f : to[b]){
        if(comp[a].find(f) != comp[a].end()) continue;
        to[a].insert(f);
        int pf = find(f);
        if(to[pf].find(a) != to[pf].end()){
            todo.push_back({pf, a});
        }
        pfrom[pf].erase(b);
        pfrom[pf].insert(a);
    }
    to[b].clear();
    for (auto f : comp[b]) {
        comp[a].insert(f);
        to[a].erase(f);
    }
    comp[b].clear();
    for (auto f : pfrom[b]) {
        pfrom[a].insert(f);
        if(pfrom[f].find(a) != pfrom[f].end()){
            todo.push_back({f, a});
        }
    }
    pfrom[b].clear();
    
    par[b] = a;

    res += (-par[a]) * ((-par[a]) - 1);
    res += to[a].size() * (-par[a]);
}

signed main()
{
    int n, m; cin >> n >> m;
    par.assign(n, -1);
    to.assign(n, {});
    pfrom.assign(n, {});
    comp.assign(n, {});
    FOR(i, n) comp[i].insert(i);
    while(m--){
        int a, b; cin >> a >> b; a--; b--; // a -> b
        int pa = find(a), pb = find(b);
        if(pa == pb) continue;
        if(pfrom[pb].find(pa) != pfrom[pb].end()){
            todo.push_back({a, b});
        }
        else{
            if(to[pb].find(a) == to[pb].end()){
                to[pb].insert(a);
                pfrom[pa].insert(pb);
                res += (-par[pb]);
            }
        }
        while(todo.size()){
            auto [x, y] = todo.back(); todo.pop_back();
            if(find(x) == find(y)) continue;
            uni(x, y);
        }
        cout << res << "\n";
    }
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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