제출 #1037313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1037313		Macker	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	0 / 100	1 ms	344 KiB

joitter2

#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;

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()) to[a].insert(f);
        int pf = find(f);
        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);
    }
    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()){
            uni(a, b);
        }
        else{
            if(to[pb].find(a) == to[pb].end()){
                to[pb].insert(a);
                pfrom[pa].insert(pb);
                res += (-par[pb]);
            }
        }
        cout << res << endl;
    }
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83