제출 #1041436

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

joitter2

#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll INF = 1e9;
const ll MAXN = 1e5+100;
set <ll> s[MAXN];
set <pll> rev[MAXN];
set <ll> edge[MAXN];
ll dsu[MAXN];
ll ans;
vector <pll> all;
void join(ll x,ll y){
    x = dsu[x],y = dsu[y];
    if (x==y)return;
    // cout<<x<<' '<<y<<'\n';
    if (sz(s[x]) < sz(s[y]))swap(x,y);
    for (auto it = rev[x].lower_bound(MP(y,0));it != rev[x].end() && (*it).fi == y;it=rev[x].erase(it)){
        ans -= sz(s[x]);
    }
    for (auto it = rev[y].lower_bound(MP(x,0));it != rev[y].end() && (*it).fi == x;it=rev[y].erase(it)){
        ans -= sz(s[y]);
    }
    ans += sz(s[x]) * sz(s[y]) * 2;
    ans += sz(rev[x]) * sz(s[y]) + sz(rev[y]) * sz(s[x]);
    for (auto z:rev[y]){
        if (rev[x].insert(z).se == 0){
            ans -= sz(s[x]) + sz(s[y]);
        }
        edge[z.fi].erase(y);
        edge[z.fi].insert(x);
        if (edge[x].find(z.fi) != edge[x].end()){
            all.push_back(MP(x,z.fi));
        }
    }
    for (auto z:edge[y]){
        edge[x].insert(z);
        if (z!=x){
            for (auto it = rev[z].lower_bound(MP(y,0));it != rev[z].end() && (*it).fi == y;it=rev[z].erase(it)){
                all.push_back(MP(x,(*it).se));
            }
            for (auto z1:all)rev[z].insert(z1);
        }
    }
    edge[x].erase(y);
    edge[x].erase(x);
    for (auto z:s[y]){
        dsu[z] = x;
        s[x].insert(z);
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    ll n,m;
    cin>>n>>m;
    for (ll i = 1;i <= n;i ++){
        s[i].insert(i);
        dsu[i] = i;
    }
    for (ll j = 1;j <= m;j ++){
        ll x,y;
        cin>>x>>y;
        if (dsu[x] != dsu[y]){
            // x = dsu[x],y = dsu[y];
            edge[dsu[x]].insert(dsu[y]);
            if (rev[dsu[y]].insert(MP(dsu[x],x)).se)ans+=sz(s[dsu[y]]);
            auto tmp = rev[dsu[x]].lower_bound(MP(dsu[y],0));
            if (tmp != rev[dsu[x]].end() && (*tmp).fi == dsu[y]){
                all.push_back(MP(dsu[x],dsu[y]));
            }
            // if (rev[x].find(y) != rev[x].end()){
            //     all.push_back(MP(x,y));
            // }
            while (!all.empty()){
                join(all.back().fi,all.back().se);
                all.pop_back();
            }
        }
        cout<<ans<<'\n';
    }
}

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