Submission #1045146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045146		Andrey	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	307 ms	50256 KiB

joitter2

#include<bits/stdc++.h>
using namespace std;

set<int> haha[100001];
set<int> bruh[100001];
vector<int> no[100001];
vector<int> dsu(100001);
vector<long long> st(100001,1);
queue<pair<int,int>> wut;

int calc(int a) {
    int c = a;
    while(dsu[c] != c) {
        c = dsu[c];
    }
    int e = a;
    while(e != dsu[e]) {
        int d = dsu[e];
        dsu[e] = c;
        e = d;
    }
    return c;
}

long long ans = 0;

void merge(int a, int b) {
    a = calc(a);
    b = calc(b);
    if(a == b) {
        return;
    }
    if(haha[a].size()+bruh[a].size()+st[a] < haha[b].size()+bruh[b].size()+st[b]) {
        swap(a,b);
    }
    ans+=st[a]*st[b]*2;
    ans-=(long long)haha[a].size()*st[a];
    ans-=(long long)haha[b].size()*st[b];
    vector<int> idk(0);
    vector<int> wow(0);
    while(!haha[b].empty()) {
        int c = *haha[b].lower_bound(-INT_MAX);
        haha[b].erase(c);
        idk.push_back(c);
    }
    while(!bruh[b].empty()) {
        int c = *bruh[b].lower_bound(-INT_MAX);
        bruh[b].erase(c);
        wow.push_back(c);
    }
    for(int i = 0; i < idk.size(); i++) {
        int c = calc(idk[i]);
        if(c == a) {
            continue;
        }
        bruh[c].erase(b);
        bruh[c].insert(a);
    }
    for(int i = 0; i < idk.size(); i++) {
        if(calc(idk[i]) != a) {
            haha[a].insert(idk[i]);
        }
    }
    for(int i = 0; i < wow.size(); i++) {
        if(wow[i] != a) {
            bruh[a].insert(wow[i]);
        }   
    }
    bruh[a].erase(b);
    for(int i = 0; i < no[b].size(); i++) {
        haha[a].erase(no[b][i]);
        no[a].push_back(no[b][i]);
    }
    st[a]+=st[b];
    ans+=(long long)haha[a].size()*st[a];
    dsu[b] = a;
    for(int i = 0; i < idk.size(); i++) {
        int c = calc(idk[i]);
        if(bruh[a].find(c) != bruh[a].end()) {
            wut.push({a,c});
        }
    }
    for(int i = 0; i < wow.size(); i++) {
        int c = wow[i];
        if(bruh[c].find(a) != bruh[c].end()) {
            wut.push({a,c});
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m,a,b;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        dsu[i] = i;
        no[i].push_back(i);
    }
    for(int i = 0; i < m; i++) {
        cin >> a >> b;
        int x = a;
        a = calc(a);
        b = calc(b);
        if(a == b) {
            cout << ans << "\n";
            continue;
        }
        ans-=(long long)haha[b].size()*st[b];
        haha[b].insert(x);
        bruh[a].insert(b);
        ans+=(long long)haha[b].size()*st[b];
        if(bruh[b].find(a) != bruh[b].end()) {
            wut.push({a,b});
        }
        while(!wut.empty()) {
            pair<int,int> c = wut.front();
            wut.pop();
            merge(c.first,c.second);
        }
        cout << ans << "\n";
    }
    return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'void merge(int, int)':
joitter2.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0; i < idk.size(); i++) {
      |                    ~~^~~~~~~~~~~~
joitter2.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; i < idk.size(); i++) {
      |                    ~~^~~~~~~~~~~~
joitter2.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i = 0; i < wow.size(); i++) {
      |                    ~~^~~~~~~~~~~~
joitter2.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0; i < no[b].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~
joitter2.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i = 0; i < idk.size(); i++) {
      |                    ~~^~~~~~~~~~~~
joitter2.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i = 0; i < wow.size(); i++) {
      |                    ~~^~~~~~~~~~~~

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