Submission #1085417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085417		phong	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	13 ms	28504 KiB

joitter2

#include<bits/stdc++.h>
#define ll long long
#define int long long
const int nmax = 3e5 + 5, N = 1e6;
const ll oo = 1e18 + 5, base = 311;
const int lg = 62, tx = 26;
const ll mod = 1e9 + 7;
#define pii pair<ll, ll>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, m;
int sz[nmax];
set<int> in[nmax], out[nmax];
int r[nmax];
int get(int u){
    return r[u] ? r[u] = get(r[u]) : u;
}
ll ans = 0;
void Union(int u, int v){
    int x = get(u);
    int y = get(v);
    if(x != y){
        if(in[x].size() + out[x].size() > in[y].size() + out[y].size()) swap(x, y);
        r[x] = y;
        int it = (int) in[x].size();
        ans -= (sz[x]) * it;
        ans -= sz[x] * (sz[x] - 1);
        it = (int)in[y].size();
        ans -= (sz[y]) * it;
        ans -= sz[y] * (sz[y] - 1);
        vector<int> lis;
        for(auto p : in[x]){
            if(out[y].count(p)) lis.push_back(p);
            out[p].erase(x);
            out[p].insert(y);
            in[y].insert(p);

        }
        for(auto p : out[x]){
            if(in[y].count(p)) lis.push_back(p);
            in[p].erase(x);
            out[y].insert(p);
            in[p].insert(y);
        }
        sz[y] += sz[x];
        it = (int)in[y].size();
        ans += (sz[y]) * it;
        ans += sz[y] * (sz[y] - 1);
        for(auto p : lis) Union(u, p);
    }
}
bool check(int u, int v){
    int x = get(u);
    int y = get(v);
    return out[x].count(y) > 0;
}
pii a[nmax];

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int u, v;
        cin >> u >> v;
        a[i] = {u, v};
    }
    for(int i = 1; i <= n; ++i) sz[i] = 1;
    for(int i = 1; i <= m; ++i){
        int u = a[i].fi, v = a[i].se;
        if(get(u) == get(v)) continue;
        u = get(u); v = get(v);
        if(check(v, u)){
            out[v].erase(u);
            in[u].erase(v);
            --ans;
            Union(u, v);
        }
        else{
            ans -= sz[v] * ((int)in[v].size());
            out[u].insert(v);
            in[v].insert(u);
            ans += sz[v] * ((int)in[v].size());

        }
        cout <<ans << endl;
    }
}
/*

*/

Compilation message (stderr)

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

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