제출 #1020617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1020617		_shr104	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	0 / 100	12 ms	14476 KiB

joitter2

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 1e5+7;
vector<set<ll>> g(mxn), rg(mxn), c(mxn);
queue<pair<ll,ll>> full_edge;
ll pr[mxn], n, m, cnt = 0, sz[mxn];
ll fs(ll u) 
{
    if (u == pr[u]) return u;
    return pr[u] = fs(pr[u]);
}
void add(ll u, ll v) // u and v = set
{
    g[u].insert(v); rg[v].insert(u);
    if (g[v].count(u)) full_edge.push({u,v});
}   
ll gsz(ll u) {return c[u].size()+g[u].size()+rg[u].size();} // u = set
void us(ll u, ll v)
{
    if (gsz(u) < gsz(v)) swap(u, v);
    cnt += sz[u]*c[v].size()+sz[v]*c[u].size();
    pr[v] = u; sz[u] += sz[v];
    for (ll i : c[v]) 
    {
        if (c[u].count(i)) cnt -= sz[u];
        else c[u].insert(i);
    }
    g[u].erase(v); rg[v].erase(u);
    g[v].erase(u); rg[u].erase(v);
    for (ll i : g[v])
    {
        rg[i].erase(v);
        add(u,i);
    }
    for (ll i : rg[v])
    {
        g[i].erase(v);
        add(i,u);
    }
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {pr[i] = i; sz[i] = 1; c[i].insert(i);}
    while (m--)
    {
        ll u, v; cin >> u >> v;
        v = fs(v);
        if (fs(u) != v && !c[v].count(u))
        {
            c[v].insert(u);
            cnt += sz[v];
            u = fs(u);
            add(u,v);
            while (full_edge.size()) 
            {
                pair<ll,ll> i = full_edge.front();
                full_edge.pop();
                us(fs(i.fi),fs(i.se));
            }
        }
        cout << cnt << '\n';
    }
}   

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