제출 #1288125

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

joitter2

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <iomanip>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <map>
#define ll long long
#define X first
#define Y second
#define endl '\n'
using namespace std;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
struct nodes
{
    int par;
    vector<int> c;
    unordered_set<int> i;
};
const int MAXN=100010;
nodes node[MAXN];
int findpar(int x)
{
    if(x==node[x].par)return x;
    return node[x].par=findpar(node[x].par);
}
int sum=0;
int getconnect(int sz)
{
    return sz*(sz-1);
}
void join(int a,int b)
{
    a=findpar(a);
    b=findpar(b);
    if(a==b)return;
    //cout<<a<<' '<<b<<"begmer"<<endl;
    //cout<<node[a].c.size()<<" "<<node[b].c.size()<<endl;

    //cout<<node[a].i.size()<<" "<<node[b].i.size()<<endl;
    
    sum-=getconnect(node[a].c.size())+getconnect(node[b].c.size());
    sum-=node[a].c.size()*node[a].i.size()+node[b].c.size()*node[b].i.size();
    //cout<<sum<<endl;
    if(node[a].c.size()<node[b].c.size())node[a].c.swap(node[b].c);
    if(node[a].i.size()<node[b].i.size())node[a].i.swap(node[b].i);
    for(int x:node[b].c)
    {
        node[a].c.push_back(x);
    }
    for (int x : node[b].i)
    {
        int t = findpar(x);
        if (t == a) continue;
        node[a].i.insert(t);
    }
    //cout<<"mergedsz "<<node[a].c.size()<<" "<<node[a].i.size()<<endl;
    node[b].c.clear();
    node[b].i.clear();
    sum+=getconnect(node[a].c.size());
    sum+=node[a].c.size()*node[a].i.size();
    node[b].par=a;
    //cout<<"endmer"<<endl;
}
void connect(int a,int b)
{
    a=findpar(a);
    b=findpar(b);
    if(a==b)return;
    if(node[b].i.count(a)!=0)return;
    if(node[a].i.count(b)==0)
    {
        node[b].i.insert(a);
        sum+=node[b].c.size();
        return;
    }
    sum-=node[a].c.size();
    node[a].i.erase(b);
    node[b].i.erase(a);
    join(a,b);

}
int n,m;
signed main()
{
    speed();
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        node[i].par=i;
        node[i].c.clear();
        node[i].c.push_back(i);
        node[i].i.clear();
        
    }
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        connect(x,y);
        cout<<sum<<endl;
    }
    return 0;
}

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