oj.uz

Submission #1067264

# Submission time Handle Problem Language Result Execution time Memory
1067264 2024-08-20T13:40:11 Z _8_8_ Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 3 ms 19036 KB 
#include <bits/stdc++.h>

using namespace std;
    
typedef long long ll;
const int  N = 1e5 + 12, MOD = (int)1e9 + 7;

int n, m, p[N];
int get(int v) {
    if(p[v] == v) return v;
    return p[v] = get(p[v]);
}
set<int> s[N],g[N],t[N],gr[N];
ll cl(int v) {
    return (int)s[v].size() * 1ll * ((int)s[v].size() - 1);
}
ll d(int v) {
    return (int)s[v].size() * 1ll * (int)t[v].size();
}
ll res = 0;
void merge(int  v,int u) {
    v = get(v);
    u = get(u);
    if(v == u) return;
    res -= cl(v);
    res -= cl(u);
    res -= d(v);
    res -= d(u);
    p[v] = u;
    for(int i:s[v]) {
        s[u].insert(i);
        t[u].erase(i);
    }
    for(int i:t[v]) {
        if(s[u].find(i) != s[u].end()) {
            t[u].erase(i);
        } else {
            t[u].insert(i);
        }
    }
    g[u].erase(v);
    g[v].erase(u);
    vector<pair<int,int>> mrg;
    for(int i:g[v]) {
        if(g[i].count(u)) {
            mrg.push_back({i,u});
        }
        g[u].insert(i);
    }
    gr[v].erase(u);
    gr[u].erase(v);
    for(int i:gr[v]) {
        if(g[u].count(i)) {
            mrg.push_back({i,u});
        }
        gr[u].insert(i);
    }
    res += cl(u);
    res += d(u);
    for(auto [x,y]:mrg) {
        merge(x,y);
    }
}
void test() {
    cin >> n >> m;
    for(int i = 1;i <= n;i++) {
        p[i] = i;
        s[i].insert(i);
    }
    while(m--) {
        int a,b;
        cin >> a >> b;
        int A = get(a),B = get(b);
        if(A == B || t[B].count(a)) {
            cout << res << '\n';
            continue;
        }
        if(g[B].count(A)) {
            merge(A,B);
        } else {
            g[A].insert(B);
            gr[B].insert(A);
            t[B].insert(a);
            res += (int)s[B].size();
        }
        cout << res << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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