Submission #1085705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085705		phong	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1113 ms	161668 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], trh[nmax];
set<pii> one[nmax], two[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){
        bool ok = 0;
        if(in[x].size() + out[x].size() + one[x].size() + two[x].size() > in[y].size() + out[y].size() + one[y].size() + two[y].size()) swap(x, y);
        ans -= sz[x] * (sz[x] - 1);
        ans -= sz[y] * (sz[y] - 1);
        int it = trh[x].size();
        ans -= it * sz[x];
        it = trh[y].size();
        ans -= it * sz[y];
        in[x].erase(y);
        out[x].erase(y);
        in[y].erase(x);
        out[y].erase(x);
        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);
        }

        for(auto p : one[x]){
            if(get(p.fi) == y){
                two[y].erase(p);
            }
            else{
                one[y].insert(p);
                trh[y].insert(p.fi);
            }
        }
        for(auto p : two[x]){
            if(get(p.se) == y){
                one[y].erase(p);
                pii it = *one[v].lower_bound({p.fi, -oo});
                if(it.fi != p.fi) trh[y].erase(p.fi);
            }
            else{
                two[y].insert(p);
            }
        }
        sz[y] += sz[x];
        r[x] = y;
        it = trh[y].size();
        ans += it * sz[y];
        ans += sz[y] * (sz[y] - 1);
        for(auto p : lis) Union(x, 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)){
            cout <<ans << endl;
            continue;
        }
        u = get(u); v = get(v);
        if(!check(v, u)){
            pii it = *one[v].lower_bound({a[i].fi, -oo});
            if(it.fi != a[i].fi) ans += sz[v];
            in[v].insert(u);
            out[u].insert(v);
            one[v].insert(a[i]);
            two[u].insert(a[i]);
            trh[v].insert(a[i].fi);
        }
        else{
//                cout << i << ' ';
            Union(u, v);
        }
        cout <<ans << endl;
    }
}
/*
3 4
3 1
1 2
2 3
1 3



*/

Compilation message (stderr)

joitter2.cpp: In function 'void Union(long long int, long long int)':
joitter2.cpp:27:14: warning: unused variable 'ok' [-Wunused-variable]
   27 |         bool ok = 0;
      |              ^~
joitter2.cpp: At global scope:
joitter2.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main(){
      | ^~~~

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