Submission #1000224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000224		snpmrnhlol	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	17 / 100	5032 ms	38740 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;
    set <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);
}
bool checkedge(int x,int y){
    int compx = leader(x);
    int compy = leader(y);
    if(compx == compy)return 1;
    if(dsu[compy].boys.find(x) != dsu[compy].boys.end())return 1;
    return 0;
}
bool check(int x,int y){
    if(x == y)return 1;
    for(auto i:dsu[x].comp){
        if(dsu[y].boys.find(i) != dsu[y].boys.end()){
            return 1;
        }
    }
    return 0;
}
void connect(int x,int y){
    x = leader(x);
    y = leader(y);
    if(x == y)return;
    if(dsu[x].sz > dsu[y].sz)swap(x,y);
    ///y connected to x
    auto it = dsu[x].boys.begin();
    while(it != dsu[x].boys.end()){
        if(leader(*it) == y){
            ans-=dsu[x].sz;
            it = dsu[x].boys.erase(it);
        }else{
            it++;
        }
    }
    ///x connected to y
    for(auto i:dsu[x].comp){
        auto it = dsu[y].boys.find(i);
        if(it != dsu[y].boys.end()){
            ans-=dsu[y].sz;
            dsu[y].boys.erase(it);
        }
        dsu[y].comp.push_back(i);
    }
    ans+=1ll*dsu[x].boys.size()*dsu[y].sz;
    ans+=1ll*dsu[y].boys.size()*dsu[x].sz;
    ///x and y connected to random node
    for(auto i:dsu[x].boys){
        assert(leader(i) != y);
        if(dsu[y].boys.find(i) != dsu[y].boys.end()){
            ans-=dsu[x].sz;
            ans-=dsu[y].sz;
        }
        dsu[y].boys.insert(i);
    }
    ans+=2ll*dsu[x].sz*dsu[y].sz;
    dsu[x].comp.clear();
    dsu[x].boys.clear();
    dsu[x].p = y;
    dsu[y].sz+=dsu[x].sz;
    ///check for new connections
    for(auto i:dsu[y].boys){
        if(check(leader(i),y) && check(y,leader(i))){
            connect(leader(i),y);
            break;
        }
    }
}
void addedge(int x,int y){
    int compx = leader(x);
    int compy = leader(y);
    if(checkedge(x,y))return;
    if(check(compy,compx)){
        connect(x,y);
    }else{
        dsu[compy].boys.insert(x);
        ans+=dsu[compy].sz;
    }
}
void dbg(){
    for(int i = 0;i < n;i++){
        cout<<"dsuinvestigate:"<<i<<'\n';
        cout<<dsu[i].p<<' '<<dsu[i].sz<<'\n';
        for(auto j:dsu[i].boys)cout<<j<<' ';cout<<'\n';
        for(auto j:dsu[i].comp)cout<<j<<' ';cout<<'\n';
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    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;
}
/**
5 20
4 2
1 5
2 3
2 5
3 2
3 1
4 5
1 2
5 2
1 4
4 1
3 4
5 1
2 4
2 1
4 3
1 3
5 4
3 5
5 3

**/

Compilation message (stderr)

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

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