oj.uz

Submission #834031

# Submission time Handle Problem Language Result Execution time Memory
834031 2023-08-22T10:15:53 Z FEDIKUS Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 488 ms 1048576 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int maxn=1e5+10;

int siz[maxn];
int dsu[maxn];
multiset<int> ideu[maxn];
multiset<int> onide[maxn];

int cale(int a){
    a==dsu[a] ? a:dsu[a]=cale(dsu[a]);
}
void join(int a,int b){ // b ide na a
    a=cale(a); b=cale(b);
    if(a==b) return;
    dsu[b]=a;
    siz[a]+=siz[b];
}

int main(){
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++) siz[i]=1;
    for(int i=1;i<=n;i++) dsu[i]=i;
    ll res=0;
    for(int i=0;i<m;i++){
        int a,b; cin>>a>>b;
        a=cale(a); b=cale(b);
        if(a==b){ // nista
            cout<<res<<"\n";
            continue;
        }
        if(onide[b].find(a)==onide[b].end()){ // nisam ih spojio
            onide[a].emplace(b);
            ideu[b].emplace(a);
            res+=siz[b];
            cout<<res<<"\n";
            continue;
        }
        // spajam ih
        /*
            0. sredi da b ne ide u a
            0.5. fixujem resenje za ove sto idu unutra i izmedju njih
            1. uzmem onog u koga je islo manje i sve koji su isli u njega promenim da ipak idu u veceg
            3. promenim u dsu da je cale onaj u koga je islo vise
            4. ako je cale isao u manje uradim swap
            5. iz drugog prebacim u caleta u sta idu
        */
        // 0.
        res-=siz[a]*ideu[a].count(b);
        ideu[a].erase(b);
        onide[b].erase(a);
        // 0.5.
        res+=siz[b]*ll(ideu[a].size());
        res+=siz[a]*ll(ideu[b].size());
        res+=2*siz[a]*siz[b];
        // 1.
        if(ideu[a].size()<ideu[b].size()) swap(a,b); // a mi je onaj koji postaje cale
        for(int i:ideu[b]){ 
            onide[i].erase(b);
            onide[i].emplace(a);
        }
        // 3.
        join(a,b);
        // 4.
        if(onide[a].size()<onide[b].size()){
            swap(onide[a],onide[b]);
        }
        // 5.
        for(int i:onide[b]) onide[a].emplace(i);

        cout<<res<<"\n";
    }
    return 0;
}

Compilation message

joitter2.cpp: In function 'int cale(int)':
joitter2.cpp:15:1: warning: no return statement in function returning non-void [-Wreturn-type]
   15 | }
      | ^

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Runtime error 488 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 488 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Runtime error 488 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -