oj.uz

Submission #260567

# Submission time Handle Problem Language Result Execution time Memory
260567 2020-08-10T14:20:56 Z doowey Making Friends on Joitter is Fun (JOI20_joitter2) C++14
0 / 100
 27 ms 42752 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 10;
vector<int> nds[N];
set<int> out[N];
set<int> in[N];
set<int> so[N];
set<int> si[N];
int par[N];
int sz[N];

ll res = 0;

int fin(int x){
    if(par[x]==x)
        return x;
    return par[x]=fin(par[x]);
}

ll f(int x){
    return x * 1ll * (x - 1);
}

void join(int a, int b){
    a = fin(a);
    b = fin(b);
    if(a == b)
        return;
    if(sz[a] > sz[b]) swap(a, b);
    res -= f(sz[a]);
    res -= f(sz[b]);
    res -= in[b].size() * 1ll * sz[b];
    res -= in[a].size() * 1ll * sz[a];
    for(auto v : nds[a]){
        nds[b].push_back(v);
        auto it = out[v].lower_bound(b);
        if(it != out[v].end() && (*it) == b){
            in[b].erase(v);
            out[v].erase(it);
        }
    }
    nds[a].clear();
    for(auto y : in[a]){
        if(fin(y) == b){
            out[y].erase(a);
        }
        else{
            out[y].erase(a);
            out[y].insert(b);
            in[b].insert(y);
        }
    }
    in[a].clear();
    for(auto v : so[a]){
        if(v == b){
            si[v].erase(a);
            continue;
        }
        else{
            si[v].erase(a);
            si[v].insert(b);
            so[b].insert(v);
        }
    }
    so[a].clear();
    for(auto v : si[a]){
        if(v == b){
            so[v].erase(a);
            continue;
        }
        else{
            so[v].erase(a);
            so[v].insert(b);
            si[b].insert(v);
        }
    }
    si[a].clear();
    par[a] = b;
    sz[b] += sz[a];
    res += in[b].size() * 1ll * sz[b];
    res += f(sz[b]);
}

void add_edge(int u, int v){
    int uf = fin(u);
    int vf = fin(v);
    if(uf == vf) return;
    so[uf].insert(vf);
    si[vf].insert(uf);
    if(out[u].count(vf)){
        return;
    }
    res += sz[vf];
    out[u].insert(vf);
    in[vf].insert(u);

    if(so[uf].count(vf) && so[vf].count(uf)){
        join(uf, vf);
    }
}

int main(){
    fastIO;
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n ; i ++ ){
        nds[i].push_back(i);
        par[i]=i;
        sz[i]=1;
    }
    int u, v;
    for(int i = 0; i < m ; i ++ ){
        cin >> u >> v;
        add_edge(u, v);
        cout << res << "\n";
    }
    return 0;
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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