oj.uz

Submission #1117223

# Submission time Handle Problem Language Result Execution time Memory
1117223 2024-11-23T02:40:53 Z vjudge1 Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 3 ms 15040 KB 
#include<bits/stdc++.h>
using namespace std;
int par[100100],sz[100100],ans;
set<int>adj[100100],radj[100100],st[100100];
queue<pair<int,int>> ops;
int abp(int a){
    return par[a]?par[a]=abp(par[a]):a;
}
void weak(int a,int b){
    adj[a].insert(b);
    radj[b].insert(a);
    if(adj[b].count(a))
        ops.push({a,b});
}
inline int ssz(int x){
    return st[x].size()+radj[x].size()+adj[x].size();
}
void merge(int a,int b){
    if(a==b)return;
    ans+=sz[a]*st[b].size()+sz[b]*st[a].size();
    if(ssz(a)<ssz(b))swap(a,b);
    par[b]=a;sz[a]+=sz[b];
    for(auto i:st[b])
        if(st[a].count(i))
            ans-=sz[a];
        else st[a].insert(i);
    adj[a].erase(b);
    adj[b].erase(a);
    radj[a].erase(b);
    radj[b].erase(a);
    for(auto i:adj[b])
        radj[i].erase(b),
        weak(a,i);
    for(auto i:radj[b])
        adj[i].erase(b),
        weak(i,a);
}
void dostuf(int a,int b){
    b=abp(b);
    if(abp(a)!=b&&!st[b].count(a)){
        st[b].insert(a);
        ans+=sz[b];
        a=abp(a);
        weak(a,b);
        while(ops.size()){
            auto[a,b]=ops.front();
            ops.pop();merge(a,b);
        }
    }
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        st[i].insert(i),sz[i]=1;
    while(m--){
        int a,b;
        cin>>a>>b;
        dostuf(a,b);
        cout<<ans<<'\n';
    }
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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