Submission #612404

#	Time	Username	Problem	Language	Result	Execution time	Memory
612404		alireza_kaviani	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	21 ms	20656 KiB

joitter2

#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
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83