제출 #869083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
869083		Leo121	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	100 / 100	543 ms	65384 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;
    set<int> in2;
    int sum_in;
    SML () {
        sum_in = 0;
    }
};

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

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

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

bool isSameSet(int i, int 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(comp[x]->in.size() + comp[x]->out.size() + comp[x]->in2.size() > comp[y]->in.size() + comp[y]->out.size() + comp[y]->in2.size()) swap(x, y);
    adi_edg -= ll(comp[y]->sum_in) * ll(setSize[y] - 1);
    adi_edg -= ll(comp[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);
    comp[y]->sum_in += comp[x]->sum_in;
    for(auto [key, val] : comp[x]->in){
        if(key == x) continue;
        if(key == y){
            comp[key]->out.erase(x);
            ori_edg -= val;
            comp[y]->sum_in -= val;
            continue;
        }
        comp[key]->out.erase(x);
        comp[key]->out[y] += val;
        if(comp[y]->out.count(key))
            q.push(mp(y, key));
        comp[y]->in[key] += val;
    }
    for(auto [key, val] : comp[x]->out){
        if(key == x) continue;
        if(key == y){
            comp[key]->in.erase(x);
            ori_edg -= val;
            comp[y]->sum_in -= val;
            continue;
        }
        comp[key]->in.erase(x);
        comp[key]->in[y] += val;
        if(comp[y]->in.count(key))
            q.push(mp(y, key));
        comp[y]->out[key] += val;
    }
    for(auto val : comp[x]->in2){
        int s = findSet(val);
        if(s == x) continue;
        if(s == y) continue;
        if(comp[y]->in2.count(val)){
            ori_edg --;
            comp[y]->sum_in --;
            comp[y]->in[s] --;
            comp[s]->out[y] --;
            continue;
        }
        comp[y]->in2.insert(val);
    }
    p[x] = y;
    setSize[y] += setSize[x];
    com_gra += ll(setSize[y]) * ll(setSize[y] - 1);
    adi_edg += ll(comp[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[x]->in.count(y)){
            if(comp[y]->in2.count(u)){
                answer();
                continue;
            }
            ori_edg ++;
            adi_edg += ll(setSize[y] - 1);
            comp[y]->sum_in ++;
            comp[y]->in[x] ++;
            comp[x]->out[y] ++;
            comp[y]->in2.insert(u);
            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();
        ///cout << '\n';
    }

    return 0;
}

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