Submission #1000058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000058		snpmrnhlol	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	6 ms	17500 KiB

joitter2

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
typedef long long ll;
ll ans = 0;
int n,m;
struct DSU{
    int p,sz,nr;
    set <pair<int,int>> boys;
    vector <int> comp;
}dsu[N];
int leader(int x){
    if(x == dsu[x].p)return x;
    return dsu[x].p = leader(dsu[x].p);
}
void connect(int x,int y){
    //cout<<"MERGE:"<<x<<' '<<y<<'\n';
    x = leader(x);
    y = leader(y);
    if(x == y)return;
    if(dsu[x].sz > dsu[y].sz)swap(x,y);
    for(auto i:dsu[x].comp){
        dsu[y].comp.push_back(i);
    }
    if(dsu[x].boys > dsu[y].boys)swap(x,y);
    set<pair<int,int>>::iterator id = dsu[y].boys.begin();
    while(id != dsu[y].boys.end()){
        auto i = *id;
        int u = leader(i.first);
        int w = leader(i.second);
        if((u == x || u == y) && (w == x || w == y)){
            assert(u != w);
            if(w == y){
                ans-=dsu[y].sz;
                dsu[y].nr--;
            }else{
                ans-=dsu[x].sz;
                dsu[x].nr--;
            }
            id = next(id);
            dsu[y].boys.erase(i);
        }else{
            id++;
        }
    }
    for(auto i:dsu[x].boys){
        int u = leader(i.first);
        int w = leader(i.second);
        if((u == x || u == y) && (w == x || w == y)){
            assert(u != w);
            if(w == y){
                ans-=dsu[y].sz;
                dsu[y].nr--;
            }else{
                ans-=dsu[x].sz;
                dsu[x].nr--;
            }
        }else{
            dsu[y].boys.insert(i);
        }
    }
    dsu[x].boys.clear();
    ans+=2ll*dsu[x].sz*dsu[y].sz;
    ans+=1ll*dsu[x].nr*dsu[y].sz;
    ans+=1ll*dsu[x].sz*dsu[y].nr;
    dsu[x].p = y;
    dsu[x].nr+=dsu[y].nr;
    dsu[y].sz+=dsu[x].sz;
}
bool checkedge(int x,int y){
    int compx = leader(x);
    int compy = leader(y);
    if(compx == compy)return 1;
    set<pair<int,int>>::iterator it = dsu[compx].boys.lower_bound({x,-1});
    while(it != dsu[compx].boys.end() && it->first == x){
        if(leader(it->second) == compy)return 1;
        it++;
    }
    return 0;
}
void addedge(int x,int y){
    int compx = leader(x);
    int compy = leader(y);
    if(checkedge(x,y))return;
    if(checkedge(y,x)){
        connect(x,y);
    }else{
        dsu[compx].boys.insert({x,y});
        dsu[compy].nr++;
        ans+=dsu[compy].sz;
    }
}
void dbg(){
    for(int i = 0;i < n;i++){
        cout<<"dsuinvestigate:"<<i<<'\n';
        cout<<dsu[i].p<<' '<<dsu[i].sz<<' '<<dsu[i].nr<<'\n';
        for(auto j:dsu[i].boys)cout<<j.first<<' '<<j.second<<'\n';cout<<'\n';
        for(auto j:dsu[i].comp)cout<<j<<' ';cout<<'\n';
    }
}
int main(){
    cin>>n>>m;
    for(int i = 0;i < n;i++){
        dsu[i] = {i,1};
        dsu[i].comp.push_back(i);
    }
    for(int i = 0;i < m;i++){
        int u,w;
        cin>>u>>w;
        u--;w--;
        addedge(u,w);
        //dbg();
        cout<<ans<<'\n';
    }
    return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'void dbg()':
joitter2.cpp:97:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   97 |         for(auto j:dsu[i].boys)cout<<j.first<<' '<<j.second<<'\n';cout<<'\n';
      |         ^~~
joitter2.cpp:97:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   97 |         for(auto j:dsu[i].boys)cout<<j.first<<' '<<j.second<<'\n';cout<<'\n';
      |                                                                   ^~~~
joitter2.cpp:98:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   98 |         for(auto j:dsu[i].comp)cout<<j<<' ';cout<<'\n';
      |         ^~~
joitter2.cpp:98:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   98 |         for(auto j:dsu[i].comp)cout<<j<<' ';cout<<'\n';
      |                                             ^~~~

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