제출 #1235645

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

joitter2

#pragma GCC optimize ("O3")
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#include <cassert>
#include<algorithm>
#include <cstring>
#include<unordered_set>
#include<queue>
#include<unordered_map>
#include<numeric>
#include <list>
#include <bitset>
using namespace std;
#define int long long
#define pii pair<int,int>
#define LL long long
int n, m;
int ans = 0;
vector<int>par;
vector<set<int>>groups_followers;
//this group's inividual followers
vector<set<int>>to_big;
vector<set<int>>from_big;
//between groups
queue<pii>q;
int get(int x) { return (par[x] < 0 ? x : (par[x] = get(par[x]))); }
void add_edge(int a, int b){
    a = get(a);
    b = get(b);
    //groups 
    to_big[a].insert(b);
    from_big[b].insert(a);
    if(to_big[b].count(a))
        q.push({a, b});
}

void merge(int a, int b) {
    a = get(a);
    b = get(b);
    if(a == b) return;
    if(groups_followers[a].size() + to_big[a].size() + from_big[a].size() > groups_followers[b].size() + to_big[b].size() + from_big[b].size()) {
        //you'll need to change group's individual followers, group followers, following groups
        swap(a, b);
    }
    //cout << a << " " << b << endl;
    //merge a INTO b

    //add answer
    //All of a's followers follow b, 
    //followers inside group count as well
   // cout << ans << endl;
   /*
       for(int i : groups_followers[b]){
        cout << i << endl;
    }
   */

   // cout << -par[a] << " " << groups_followers[b].size() << " " << (-par[b]) << " " << groups_followers[a].size() << endl;
    ans += (groups_followers[a].size() * (-par[b]) + groups_followers[b].size() * (-par[a]));
    //cout << ans << endl;
    par[b] += par[a];
    par[a] = b;
    for(int i : groups_followers[a]){
        if(groups_followers[b].count(i)){
            //this was already following everyone in group b, subtract it out
            ans -= (-par[b]);
        }
        groups_followers[b].insert(i);
    }
    //do we need this?
    to_big[a].erase(b);
    to_big[b].erase(a);
    from_big[a].erase(b);
    from_big[b].erase(a);
    for(int i : to_big[a]){
        from_big[i].erase(a);
        add_edge(b, i);
    }
    for(int i : from_big[a]){
        to_big[i].erase(a);
        add_edge(i, b);
    }
}
int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin >> n >> m;
    par = vector<int>(n + 1, -1);
    groups_followers = vector<set<int>>(n + 1);
    to_big = vector<set<int>>(n + 1);
    from_big = vector<set<int>>(n + 1);
    for(int i = 1; i <= n; ++i)
        groups_followers[i].insert(i);
    while(m--){
        int a, b;
        cin >> a >> b;

        if(m == 0){
            // cout << "m=0:\n";
             /*
                    for(int i = 1;i <= 3; ++i){
                 cout << par[i] << " ";
             }
                             for(int i : groups_followers[4]){
                 cout << i << " ";
             }
             */


             //cout << endl;
        }


        //you need both, a cannot be in b and a cannot follow anyone in b's group
        if(groups_followers[get(b)].count(a) || get(a) == get(b)){
            cout << ans << "\n";
            continue;
        }
        groups_followers[get(b)].insert(a);
        ans += (-par[get(b)]);
        add_edge(get(a), get(b));
        while(!q.empty()){
            a = q.front().first;
            b = q.front().second;
            q.pop();
            //cout << a << " " << b << endl;
            merge(a, b);
        }
        cout << ans << "\n";

    }
}

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