Submission #1288129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288129		bbbiros	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	5 ms	9032 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 int 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);
    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