oj.uz

Submission #612404

# Submission time Handle Problem Language Result Execution time Memory
612404 2022-07-29T14:20:37 Z alireza_kaviani Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 21 ms 20656 KB 
#include <bits/stdc++.h>
using namespace std;

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

#define all(x)      (x).begin(),(x).end()
#define X           first
#define Y           second
#define sep         ' '
#define endl        '\n'
#define SZ(x)       ll(x.size())

const ll MAXN = 1e5 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

ll n , m , ans , sz[MAXN] , par[MAXN];
set<int> inDeg[MAXN] , outDeg[MAXN];
vector<pii> Q;

int Find(int v){
    return (par[v] == -1 ? v : par[v] = Find(par[v]));
}

void Union(int v , int u){
    v = Find(v); u = Find(u);
    if(v == u)  return;
    if(sz[v] < sz[u])   swap(v , u);
    ans -= sz[v] * SZ(inDeg[v]) + sz[u] * SZ(inDeg[u]);
    par[u] = v; sz[v] += sz[u];
    for(auto &i : inDeg[u]){
        inDeg[v].insert(i);
        outDeg[Find(i)].insert(v);
        if(Find(i) != v && Find(i) != u && outDeg[v].find(Find(i)) != outDeg[v].end()){
            Q.push_back({v , i});
        }
    }
    for(auto &i : outDeg[u]){
        outDeg[v].insert(i);
    }
    ans += sz[v] * SZ(inDeg[v]);
}

void Add(int v , int u){
    u = Find(u);
    if(Find(v) == u)  return;
    if(inDeg[u].find(v) != inDeg[u].end()){
        return;
    }
    if(outDeg[u].find(Find(v)) != outDeg[u].end()){
        Q.push_back({v , u});
        while(!Q.empty()){
            pii A = Q.back(); Q.pop_back();
            Union(A.X , A.Y);
        }
        return;
    }
    inDeg[u].insert(v);
    outDeg[Find(v)].insert(u);
    ans += sz[u];
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    fill(par , par + MAXN , -1);
    fill(sz , sz + MAXN , 1);
    for(int i = 0 ; i < MAXN ; i++){
        inDeg[i].insert(i);
        outDeg[i].insert(i);
    }

    cin >> n >> m;
    for(int i = 0 ; i < m ; i++){
        int v , u;
        cin >> v >> u;
        Add(v , u);
        cout << ans << endl;
    }

    return 0;
}
/*

*/

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 20564 KB Output is correct
2 Correct 18 ms 20564 KB Output is correct
3 Incorrect 21 ms 20656 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 20564 KB Output is correct
2 Correct 18 ms 20564 KB Output is correct
3 Incorrect 21 ms 20656 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 20564 KB Output is correct
2 Correct 18 ms 20564 KB Output is correct
3 Incorrect 21 ms 20656 KB Output isn't correct
4 Halted 0 ms 0 KB -