Submission #868824

#	Time	Username	Problem	Language	Result	Execution time	Memory
868824		Leo121	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	1 ms	2396 KiB

joitter2

#include <bits/stdc++.h>

#define pb push_back
#define rbg(v) v.rbegin()
#define bg(v) v.begin()
#define all(v) bg(v), v.end()
#define sz(v) int(v.size())
#define mp make_pair
#define fi first
#define se second
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define for0(i, n) forn(i, 0, n - 1)
#define for1(i, n) forn(i, 1, n)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
#define far0(i, n) fora(i, n - 1, 0)
#define far1(i, n) fora(i, n, 1)
#define foru(i, v) for(auto & i : v)
#define lb lower_bound
#define ub upper_bound
#define sz(v) int(v.size())
#define ord1(s, n) s + 1, s + int(n) + 1
#define ord0(s, n) s, s + int(n)
#define debug(x) /// cout << #x << " = " << x << endl

using namespace std;

///#include <bits/extc++.h>
///using namespace __gnu_pbds;
///typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef long double ld;
typedef double db;
typedef long long lli;
///typedef __int128 Int;

const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
///const int inf = 1e4

const int MX = 1e5 + 2;

struct SML{
    map<int, int> in;
    map<int, int> out;
    int sum_in;
    SML () {
        sum_in = 0;
    }
};

SML * comp[MX];
int p[MX], r[MX], setSize[MX], apu[MX];
ll ori_edg, com_gra, adi_edg;
queue<pii> q;

void UnionFind(int N){
    for1(i, N) p[i] = i, setSize[i] = 1, apu[i] = i;
}

int findSet(int i){
    debug(i);
    return (p[i] == i) ? i : (p[i] = findSet(p[i]));
}

bool isSameSet(int i, int j){
    debug(i);
    debug(j);
    return findSet(i) == findSet(j);
}

void unionSet(int i, int j){
    if(isSameSet(i, j)) return;
    int x = findSet(i), y = findSet(j);
    if(r[x] > r[y]) swap(x, y);
    adi_edg -= ll(comp[apu[y]]->sum_in) * ll(setSize[y] - 1);
    adi_edg -= ll(comp[apu[x]]->sum_in) * ll(setSize[x] - 1);
    com_gra -= ll(setSize[x]) * ll(setSize[x] - 1);
    com_gra -= ll(setSize[y]) * ll(setSize[y] - 1);
    bool change = 0;
    int w = x, z = y;
    if(comp[apu[w]]->in.size() + comp[apu[w]]->out.size() > comp[apu[z]]->in.size() + comp[apu[z]]->out.size()){
        change = 1;
        swap(w, z);
    }
    comp[apu[z]]->sum_in += comp[apu[w]]->sum_in;
    for(auto [key, val] : comp[apu[w]]->in){
        int s = findSet(key);
        if(s == w) continue;
        if(s == z){
            ori_edg -= val;
            comp[apu[z]]->sum_in -= val;
            continue;
        }
        if(comp[apu[z]]->out.count(key))
            q.push(mp(w, key));
        comp[apu[z]]->in[key] += val;
    }
    for(auto [key, val] : comp[apu[w]]->out){
        int s = findSet(key);
        if(s == w) continue;
        if(s == z){
            ori_edg -= val;
            comp[apu[z]]->sum_in -= val;
            continue;
        }
        if(comp[apu[z]]->in.count(key))
            q.push(mp(w, key));
        comp[apu[z]]->out[key] += val;
    }
    p[x] = y;
    if(change) apu[y] = apu[x];
    if(r[x] == r[y]) ++ r[y];
    setSize[y] += setSize[x];
    com_gra += ll(setSize[y]) * ll(setSize[y] - 1);
    adi_edg += ll(comp[apu[y]]->sum_in) * ll(setSize[y] - 1);
}

void answer(){
    cout << ori_edg + adi_edg + com_gra << '\n';
}

void solve(){
    int n, m;
    cin >> n >> m;
    for1(i, n) comp[i] = new SML();
    UnionFind(n);
    while(m --){
        int u, v;
        cin >> u >> v;

        if(isSameSet(u, v)){
            answer();
            continue;
        }
        int x, y;
        x = findSet(u), y = findSet(v);
        if(!comp[apu[y]]->out.count(u)){
            if(comp[apu[y]]->in.count(u)){
                answer();
                continue;
            }
            ori_edg ++;
            adi_edg += ll(setSize[y] - 1);
            comp[apu[y]]->in[u] ++;
            comp[apu[y]]->sum_in ++;
            comp[apu[x]]->out[v] ++;
            answer();
            continue;
        }
        unionSet(u, v);
        while(!q.empty()){
            unionSet(q.front().fi, q.front().se);
            q.pop();
        }
        answer();
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); ///cout.tie(0);
    int t = 1;
    ///cin >> t;
    for1(i, t){
        ///cout << "Case #" << i << ": ";
        solve();
    }

    return 0;
}

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