제출 #1000263

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

joitter2

#include<bits/stdc++.h>
//#define cin fin
//#define cout fout
using namespace std;
//ifstream fin("a.in");
//ofstream fout("a.out");
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];
set <int> edges[N];
multiset <int> compedges[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;
    if(compedges[x].find(y) != compedges[x].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[x].boys.size() + compedges[x].size() > dsu[y].sz + dsu[y].boys.size() + compedges[y].size())swap(x,y);
    ///check new edges
    int nr1 = -1;
    for(int i = 0;i < n;i++){
        if(check(leader(i),y) && check(x,leader(i)) && leader(i) != y){
            nr1 = leader(i);
        }
        if(check(leader(i),x) && check(y,leader(i)) && leader(i) != y){
            nr1 = leader(i);
        }
    }
    ///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);
            edges[*it].erase(x);
            compedges[y].erase(compedges[y].find(x));
        }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);
            edges[*it].erase(y);
            compedges[x].erase(compedges[x].find(y));
        }
        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);
        edges[i].erase(x);
        compedges[leader(i)].erase(compedges[leader(i)].find(leader(x)));
        edges[i].insert(y);
        compedges[leader(i)].insert(leader(y));
    }
    for(auto i:compedges[x]){
        compedges[y].insert(i);
    }
    ans+=2ll*dsu[x].sz*dsu[y].sz;
    dsu[x].p = y;
    dsu[y].sz+=dsu[x].sz;
    dsu[x].comp.clear();
    dsu[x].boys.clear();
    compedges[x].clear();
    ///check for new connections
    for(auto i:dsu[y].boys){
        if(check(leader(i),y) && check(y,leader(i)) && nr1 != -1){
            nr1 = leader(i);
        }
    }
    if(nr1 != -1){
        connect(y,nr1);
    }
}
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);
        edges[x].insert(compy);
        compedges[compx].insert(compy);
        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

**/

컴파일 시 표준 에러 (stderr) 메시지

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

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