oj.uz

Submission #841242

# Submission time Handle Problem Language Result Execution time Memory
841242 2023-09-01T11:58:49 Z Ahmed57 Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 10 ms 14420 KB 
#include <bits/stdc++.h>

using namespace std;
set<int> ch[100001],adj[100001],rev[100001];
long long ans = 0;
long long pr[100001],sz[100001];
queue<pair<int,int>> to;
void insertcon(int x,int y){
    adj[x].insert(y);
    rev[y].insert(x);
    if(adj[y].count(x))to.push({x,y});
}
int find(int x){
    if(x==pr[x])return x;
    return pr[x] = find(pr[x]);
}
int dsu_sz(int x){
    return ch[x].size()+adj[x].size()+rev[x].size();
}
void mergegroup(int a,int b){
    if(a==b)return ;
    if(dsu_sz(a)<dsu_sz(b))swap(a,b);
    ans+=sz[a]*ch[b].size()+sz[b]*ch[a].size();
    pr[b] = a;sz[a]+=sz[b];
    for(auto i:ch[b]){
        if(ch[a].count(i))ans-=sz[a];
        else ch[a].insert(i);
    }
    adj[a].erase(b);rev[b].erase(a);
    adj[b].erase(a);rev[a].erase(b);
    for(auto i:adj[b]){
        rev[i].erase(b);
        insertcon(a,i);
    }for(auto i:rev[b]){
        adj[i].erase(b);
        insertcon(i,a);
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        pr[i] = i;
        sz[i] = 1;
        ch[i].insert(i);
    }
    for(int i = 0;i<m;i++){
        int a,b;cin>>a>>b;
        b = find(b);
        if(find(a)!=b&&!ch[b].count(a)){
            ch[b].insert(a);
            ans+=sz[b];
            a = find(a);
            insertcon(a,b);
            while(!to.empty()){
                int A = to.front().first;
                int B = to.front().second;
                mergegroup(A,B);
                to.pop();
            }
        }
        cout<<ans<<endl;
    }
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14316 KB Output is correct
3 Correct 7 ms 14396 KB Output is correct
4 Correct 6 ms 14292 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 7 ms 14292 KB Output is correct
7 Incorrect 10 ms 14420 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14316 KB Output is correct
3 Correct 7 ms 14396 KB Output is correct
4 Correct 6 ms 14292 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 7 ms 14292 KB Output is correct
7 Incorrect 10 ms 14420 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14316 KB Output is correct
3 Correct 7 ms 14396 KB Output is correct
4 Correct 6 ms 14292 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 7 ms 14292 KB Output is correct
7 Incorrect 10 ms 14420 KB Output isn't correct
8 Halted 0 ms 0 KB -