Submission #624026

#	Time	Username	Problem	Language	Result	Execution time	Memory
624026		radal	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	7 ms	9684 KiB

joitter2

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 1e5+10,mod = 998244353,inf = 1e9+10,sq = 700;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k /= 2;
    } 
    return z; 
}
int par[N],sz[N];
ll ans;
set<pll> in[N],out[N];
int getpar(int v){
    if (v == par[v]) return v;
    return par[v] = getpar(par[v]);
}
inline void mg(int u,int v){
    if (getpar(u) == getpar(v)) return;
    ans += 2ll*sz[u]*sz[v];
    while (!out[v].empty()){
        auto it = out[v].lower_bound({u,0});
        if (it == out[v].end() || it->X != u) break;
        ans -= sz[u];
        out[v].erase(it);
    }
    while (!out[u].empty()){
        auto it = out[u].lower_bound({v,0});
        if (it == out[u].end() || it->X != v) break;
        ans -= sz[v];
        out[u].erase(it);
    }
    while (!in[v].empty()){
        auto it = in[v].lower_bound({u,0});
        if (it == in[v].end() || it->X != u) break;
        in[v].erase(it);
    }
    while (!in[u].empty()){
        auto it = in[u].lower_bound({v,0});
        if (it == in[u].end() || it->X != v) break;
        in[u].erase(it);
    }
    if (out[u].size()+in[u].size() > out[v].size()+in[v].size()) swap(u,v);
    par[u] = v;
    sz[v] += sz[u];
    vector<int> nxt;
    int beg = in[v].size(),mosh = 0;
    for (pll p : out[u]){
        auto it = in[v].lower_bound({p.X,0});
        if (it != in[v].end() && it->X == p.X) nxt.pb(p.X);
        out[v].insert(p);
        in[p.X].erase({u,p.Y});
        in[p.X].insert({v,p.Y});
    }
    for (pll p : in[u]){
        out[p.X].erase({u,p.Y});
        if (in[v].find(p) != in[v].end()){
            mosh++;
            continue;
        }
        auto it = out[v].lower_bound({p.X,0});
        if (it != out[v].end() && it->X == p.X) nxt.pb(p.X);
        out[p.X].insert({v,p.Y});
        in[v].insert(p);
        ans += sz[v];
    }
    out[u].clear();
    in[u].clear();
    ans += 1ll*sz[u]*(beg-mosh);
    for (int w : nxt) mg(w,v);
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    int n,q;
    cin >> n >> q;
    rep(i,1,n+1){
        par[i] = i;
        sz[i] = 1;
    }
    while (q--){
        int u,v;
        cin >> u >> v;
        getpar(u);
        getpar(v);
        if (par[u] == par[v] || out[par[u]].find({par[v],u}) != out[par[u]].end()){
            cout << ans << endl;
            continue;
        }
        out[par[u]].insert({par[v],u});
        in[par[v]].insert({par[u],u});
        u = getpar(u);
        v = getpar(v);
        ans += sz[v];
        auto it = out[v].lower_bound({u,0});
        if (it != out[v].end() && it->X == u){
            mg(u,v);
            cout << ans << endl;
        }
        else{
            cout << ans << endl;
            continue;
        }
    }
}

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