제출 #1041483

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1041483		hotboy2703	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	17 / 100	214 ms	53216 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<<"JOIN "<<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)){
        // cout<<x<<' '<<(*it).se<<'\n';
        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)){
        // cout<<y<<' '<<(*it).se<<'\n';
        ans -= sz(s[y]);
    }
    // cout<<"BEF "<<ans<<'\n';
    ans += sz(s[x]) * sz(s[y]) * 2;
    ans += sz(rev[x]) * sz(s[y]) + sz(rev[y]) * sz(s[x]);
    // cout<<"AF "<<ans<<'\n';
    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));
        }
    }
    edge[y].erase(x);
    for (auto z:edge[y]){
        edge[x].insert(z);
        if (z!=x){
            vector <pll> tmp;
            // cout<<"REV "<<z<<'\n';
            // for (auto x:rev[z])cout<<x.fi<<' '<<x.se<<' ';
            // cout<<'\n';
            for (auto it = rev[z].lower_bound(MP(y,0));it != rev[z].end() && (*it).fi == y;it=rev[z].erase(it)){
                tmp.push_back(MP(x,(*it).se));
                // cout<<"ADDREV "<<z<<' '<<x<<' '<<(*it).se<<'\n';
            }
            // for (auto x:rev[z])cout<<x.fi<<' '<<x.se<<' ';
            // cout<<'\n';
            for (auto z1:tmp)rev[z].insert(z1);
            // for (auto x:rev[z])cout<<x.fi<<' '<<x.se<<' ';
            // cout<<'\n';
        }
    // cout<<"SUS "<<z<<' '<<x<<'\n';
    // for (auto z1:edge[z])cout<<z1<<' ';
    // cout<<'\n';
        if (edge[z].find(x) != edge[z].end()){
            // cout<<"ADD "<<x<<' '<<z<<'\n';
            all.push_back(MP(x,z));
        }
    }
    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]]);
            // if (j==6)cout<<"SUS" <<ans<<' '<<dsu[x]<<' '<<dsu[y]<<'\n';
            if (edge[dsu[y]].find(dsu[x]) != edge[dsu[y]].end()){
                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()){
                // cout<<"TRY JOIN "<<all.back().fi<<' '<<all.back().se<<'\n';
                pll u = all.back();all.pop_back();
                join(u.fi,u.se);
                // all.pop_back();
            }
        }
        cout<<ans<<'\n';
    }
}

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