oj.uz

Submission #1000221

# Submission time Handle Problem Language Result Execution time Memory
1000221 2024-06-17T06:35:42 Z Unforgettablepl Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 4 ms 11356 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long

struct UFDS{
    vector<int> p,siz;
    vector<set<pair<int,int>>> incoming,outgoing;
    UFDS(int n):p(n+1),siz(n+1,1),incoming(n+1),outgoing(n+1){iota(p.begin(),p.end(),0);}
    int findRoot(int x){
        return p[x]==x ? x : p[x]=findRoot(p[x]);
    }
    int unite(int x,int y){
        int root_x = findRoot(x);
        y = findRoot(y);
        if(y==root_x)return 0;
        if(outgoing[root_x].count({y,x}))return 0;
        auto iter = incoming[root_x].lower_bound({y,0ll});
        if(iter!=incoming[root_x].end() and iter->first==y){
            int ans = 0;
            // TODO: Merge
            while(true){
                iter = incoming[root_x].lower_bound({y,0ll});
                if(iter==incoming[root_x].end() or iter->first!=y)break;
                outgoing[y].erase({root_x,iter->second});
                incoming[root_x].erase(iter);
                ans-=siz[root_x];
            }
            ans-=siz[root_x]*incoming[root_x].size();
            ans-=siz[y]*incoming[y].size();
            ans-=siz[root_x]*(siz[root_x]-1ll);
            ans-=siz[y]*(siz[y]-1ll);
            if(incoming[root_x].size()+outgoing[root_x].size()<incoming[y].size()+outgoing[y].size())swap(root_x,y);
            p[y] = root_x;
            siz[root_x]+=siz[y];
            for(auto[a,b]:incoming[y]){
                incoming[root_x].insert({a,b});
                outgoing[a].erase({y,b});
                outgoing[a].insert({root_x,b});
            }
            for(auto[a,b]:outgoing[y]){
                outgoing[root_x].insert({a,b});
                incoming[a].erase({y,b});
                incoming[a].insert({root_x,b});
            }
            ans+=siz[root_x]*incoming[root_x].size();
            ans+=siz[root_x]*(siz[root_x]-1);
            return ans;
        }
        outgoing[root_x].insert({y,x});
        incoming[y].insert({root_x,x});
        return siz[y];
    }
};

UFDS dsu(100000);

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin >> n >> m;
    int ans = 0;
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        ans+=dsu.unite(a,b);
        cout << ans << '\n';
    }
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11356 KB Output is correct
2 Correct 4 ms 11356 KB Output is correct
3 Incorrect 4 ms 11356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11356 KB Output is correct
2 Correct 4 ms 11356 KB Output is correct
3 Incorrect 4 ms 11356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11356 KB Output is correct
2 Correct 4 ms 11356 KB Output is correct
3 Incorrect 4 ms 11356 KB Output isn't correct
4 Halted 0 ms 0 KB -