Submission #834031

#	Time	Username	Problem	Language	Result	Execution time	Memory
834031		FEDIKUS	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	0 / 100	488 ms	1048576 KiB

joitter2

#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 (stderr)

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
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83