oj.uz

답안 #568098

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
568098 2022-05-24T16:28:43 Z alvingogo 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 1 ms 212 KB 
//#define __GLIBCXX_DEBUG
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

struct no{
    int bo,sz;
    map<int,int> tb,fb;
    set<int> tp,fp;
    vector<int> ch;
};
vector<no> v;
long long ans=0;
int find(int a){
    return v[a].bo==a?a:v[a].bo=find(v[a].bo);
}
void merge(int x,int y){
    queue<pair<int,int> > q;
    q.push({x,y});
    while(!q.empty()){
        auto g=q.front();
        q.pop();
        int a=find(g.fs),b=find(g.sc);
        if(a==b){
            return;
        }
        if(v[a].sz>v[b].sz){
            swap(a,b);
        }
        ans-=1ll*v[b].tp.size()*v[b].sz;
        ans-=1ll*v[a].tp.size()*v[a].sz;
        ans-=1ll*(v[b].sz)*(v[b].sz-1);
        ans-=1ll*(v[a].sz)*(v[a].sz-1);
        for(auto y:v[a].tp){
            int u=find(y);
            if(u==b){
                continue;
            }
            v[b].tp.insert(y);
            v[u].fb.erase(a);
            v[u].fb[b]++;
        }
        for(auto y:v[a].fp){
            int u=find(y);
            if(u==b){
                continue;
            }
            v[b].fp.insert(y);
            v[u].tb.erase(a);
            v[u].tb[b]++;
        }
        for(auto y:v[a].ch){
            v[b].tp.erase(y);
            v[b].fp.erase(y);
            v[b].ch.push_back(y);
        }
        v[b].sz+=v[a].sz;
        v[a].bo=b;
        ans+=1ll*v[b].tp.size()*v[b].sz;
        ans+=1ll*(v[b].sz)*(v[b].sz-1);
        set<int> nxt;
        for(auto y:v[a].tp){
            int u=find(y);
            if(u==b){
                continue;
            }
            if(v[u].tb.find(b)!=v[u].tb.end()){
                nxt.insert(u);
            }
        }
        for(auto y:v[a].fp){
            int u=find(y);
            if(u==b){
                continue;
            }
            if(v[u].fb.find(b)!=v[u].fb.end()){
                nxt.insert(u);
            }
        }
        for(auto y:v[a].tb){
            if(y.fs!=b){
                v[b].tb[y.fs]++;
            }
        }
        for(auto y:v[a].fb){
            if(y.fs!=b){
                v[b].fb[y.fs]++;
            }
        }
        for(auto h:nxt){
            q.push({h,b});
        }
    }
    
}
signed main(){
    AquA;
    int n,m;
    cin >> n >> m;
    v.resize(n);
    for(int i=0;i<n;i++){
        v[i].bo=i;
        v[i].sz=1;
        v[i].ch.push_back(i);
    }
    for(int i=0;i<m;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        int c=find(a),d=find(b);
        if(c==d){
            continue;
        }
        else{
            if(v[d].tp.find(a)==v[d].tp.end()){
                v[d].tp.insert(a);
                ans+=v[d].sz;
                v[d].tb[c]++;
                v[c].fb[d]++;
                v[c].fp.insert(b);
                if(v[c].tb.find(d)!=v[c].tb.end()){
                    merge(a,b);
                }
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -