Submission #1278232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278232		Robert_junior	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	892 ms	192888 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define ld long double
#define ins insert
const int N = 1e6 + 7, mod = 1e9 + 7;
int pr[N], sz[N], ans = 0;
set<int>ch[N], g[N], rg[N];
queue<pair<int, int>>q;
void add(int A, int B){
    g[A].ins(B);
    rg[B].ins(A);
    if(g[B].count(A)) q.push({A, B});
}
int get(int v){
    if(pr[v] == v) return v;
    else return pr[v] = get(pr[v]);
}
int size(int v){
    return ch[v].size() + g[v].size() + rg[v].size();
}
void unite(int u, int v){
    if(u == v) return;
    if(size(u) < size(v)) swap(u, v);
    ans += sz[v] * ch[u].size() + sz[u] * ch[v].size(); 
    pr[v] = u;
    sz[u] += sz[v];
    for(int i : ch[v]){
        if(ch[u].count(i)) ans -= sz[u];
        else ch[u].ins(i);
    }
    g[u].erase(v), g[v].erase(u);
    rg[u].erase(v), rg[v].erase(u);
    for(int i : g[v]){
        rg[i].erase(v);
        add(u, i);
    }   
    for(int i : rg[v]){ 
        g[i].erase(v);
        add(i, u);
    }
}
main(){
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        sz[i] = 1;
        pr[i] = i;
        ch[i].ins(i);
    }
    while(m--){
        int u, v;
        cin>>u>>v;
        v = get(v);
        if(get(u) != v && !ch[v].count(u)){
            ch[v].ins(u);
            ans += sz[v];
            u = get(u); 
            add(u, v);
            while(q.size()){
                int a = q.front().F, b = q.front().S;
                q.pop();
                unite(get(a), get(b));
            }
        }
        cout<<ans<<'\n';
    }
}

Compilation message (stderr)

joitter2.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main(){
      | ^~~~

• Subtask 1: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 83 / 83