oj.uz

답안 #573388

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
573388 2022-06-06T13:48:24 Z socpite 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 17 ms 30804 KB 
#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;

const int maxn = 3e5+5;
const ll inf = 1e18;

int n, m;

ll ans = 0;

struct dsu{
    int root = -1;
    set<int> in;
    set<int> out;
};

dsu up[maxn];

int Find(int x){
    if(up[x].root < 0)return x;
    else{
        up[x].root = Find(up[x].root);
        return up[x].root;
    }
}

queue<pair<int, int>> edges;

void Union(int a, int b){
    ans+=up[a].root;
    up[a].in.erase(b);
    up[b].out.erase(a);
    if(up[a].in.size() + up[a].out.size() < up[b].in.size() + up[b].out.size())swap(a, b);
    ans+=1LL*up[a].root*(-up[a].root-1);
    ans+=1LL*up[b].root*(-up[b].root-1);
    ans -= 1LL*up[b].root*up[a].in.size();
    for(auto it = up[b].in.begin(); it != up[b].in.end(); it++){
        ans+=up[b].root;
        up[*it].out.erase(b);
        edges.push({*it, a});
    }
    for(auto it = up[b].out.begin(); it != up[b].out.end(); it++){
        ans+=up[*it].root;
        up[*it].in.erase(b);
        edges.push({a, *it});
    }
    up[a].root+=up[b].root;
    up[b].root = a;
    ans-=1LL*up[a].root*(-up[a].root-1);
    //cout << a << " " << b << " " << ans << endl;
}

void add(int a, int b){
    a = Find(a);
    b = Find(b);
    if(a==b)return;
    if(up[a].in.find(b) != up[a].in.end())Union(a, b);
    else{
        //cout << "sus" << endl;
        if(up[a].out.find(b) != up[a].out.end())return;
        ans -= up[b].root;
        up[a].out.insert(b);
        up[b].in.insert(a);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    while(m--){
        int a, b;
        cin >> a >> b;
        edges.push({a, b});
        while(!edges.empty()){
            auto x = edges.front();
            edges.pop();
            add(x.f, x.s);
        }
        cout << ans << "\n";
    }
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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