oj.uz

Submission #1045090

# Submission time Handle Problem Language Result Execution time Memory
1045090 2024-08-05T16:37:34 Z Andrey Making Friends on Joitter is Fun (JOI20_joitter2) C++14
0 / 100
 4 ms 13404 KB 
#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) {
    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;
        }
        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(c == a) {
            continue;
        }
        if(bruh[c].find(a) != bruh[c].end()) {
            wut.push({a,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;
}

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();
            merge(c.first,c.second);
            wut.pop();
        }
        cout << ans << "\n";
    }
    return 0;
}

Compilation message

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

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13144 KB Output is correct
2 Correct 2 ms 13148 KB Output is correct
3 Correct 2 ms 13148 KB Output is correct
4 Correct 2 ms 13148 KB Output is correct
5 Correct 4 ms 13148 KB Output is correct
6 Correct 3 ms 13144 KB Output is correct
7 Incorrect 3 ms 13404 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13144 KB Output is correct
2 Correct 2 ms 13148 KB Output is correct
3 Correct 2 ms 13148 KB Output is correct
4 Correct 2 ms 13148 KB Output is correct
5 Correct 4 ms 13148 KB Output is correct
6 Correct 3 ms 13144 KB Output is correct
7 Incorrect 3 ms 13404 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13144 KB Output is correct
2 Correct 2 ms 13148 KB Output is correct
3 Correct 2 ms 13148 KB Output is correct
4 Correct 2 ms 13148 KB Output is correct
5 Correct 4 ms 13148 KB Output is correct
6 Correct 3 ms 13144 KB Output is correct
7 Incorrect 3 ms 13404 KB Output isn't correct
8 Halted 0 ms 0 KB -