Submission #1249867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249867		thichcodedao	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++20	0 / 100	71 ms	141120 KiB

joitter2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define TruongPham int main()
#define sz 1000006
const int mod = 1e9 +7;
const int base = 31;
int n, q;
set<int> listIn[sz], listOut[sz]; // danh sach cac dinh vao va ra cua mot thanh phan lien thong
set<int> child[sz]; // child[i] la nhung thang co noi den i
int root[sz];
int numb[sz];
ll ans =0;
vector<pair<int,int>> store; // dung de luu tru cac canh vo huong
int findroot(int u)
{
    if (u==root[u]) return u;
    int rootu = findroot(root[u]);
    root[u] = rootu;
    return rootu;
}

void add(int u, int v)
{
    listOut[u].insert(v); 
    listIn[v].insert(u);
    if (listOut[v].find(u) != listOut[v].end()) // u -> v va v -> u
    {
        store.push_back({u,v});
    }
}
int total(int u)
{
    return (int)child[u].size() + (int)listIn[u].size() + (int)listOut[u].size();
    // tong so dinh trong tplt u + so dinh di vao u + so dinh tu u di ra
}
void unite(int rootu, int rootv)
{
    if (rootu == rootv)
    {
        return;
    }
    if (total(rootu) < total(rootv))
    {
        swap(rootu, rootv);
    }
    auto rootu_out = listOut[rootu].find(rootv);
    auto rootu_in = listIn[rootu].find(rootv);
    auto rootv_out = listOut[rootv].find(rootu);
    auto rootv_in = listIn[rootv].find(rootu);
    if (rootu_out != listOut[rootu].end())
    {
        listOut[rootu].erase(rootu_out);
    }
    if (rootu_in != listIn[rootu].end())
    {
        listIn[rootu].erase(rootu_in);
    }
    if (rootv_out != listOut[rootv].end())
    {
        listOut[rootv].erase(rootv_out);
    }
    if (rootv_in != listIn[rootv].end())
    {
        listIn[rootv].erase(rootv_in);
    }
    ans += (1ll* child[rootu].size() * numb[rootv] + 1ll* child[rootv].size() * numb[rootu]);
    numb[rootu] += numb[rootv];
    //ans += (1ll * numb[rootv] *(int)listIn[rootu].size() +  1ll* numb[rootu] *(int)listIn[rootv].size());
    // tien hanh noi tat ca cua v vao u
    // xoa tat ca thong tin lien quan den v
    root[rootv] = rootu;
    for (auto it: child[rootv])
    {
        if (child[rootu].find(it) != child[rootu].end())
        {
            ans -= numb[rootu]; // nhung thang co ton tai o ca rootu vaf rootv da bi cong nham 
            // mot luong la tong tplt moi
            // do truoc do chung ta co ans += numb[rootv] da bao gom nhung thang trung roi
        } else 
        {
            child[rootu].insert(it); // de kiem tra neu khi noi 1 canh ma ta da noi roi;
        }
    }
    child[rootv].clear();
    for (auto it:listIn[rootv]) // x -> rootv
    {
        if (listOut[it].find(rootv) != listOut[it].end())
        {
            listOut[it].erase(listOut[it].find(rootv));
        }
        add(it, rootu);
    }
    for (auto it:listOut[rootv]) // rootv -> x
    {
        if (listIn[it].find(rootv) != listIn[it].end())
        {
            listIn[it].erase(listIn[it].find(rootv));
        }
        add(it, rootu);
    }
    listIn[rootv].clear();
    listOut[rootv].clear();
}
TruongPham
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>q;
    for (int i=1;i<=n;i++)
    {
        root[i] = i;
        numb[i] =1;
        child[i].insert(i);
    } // khoi tao tplt dinh i
    for (int i=1;i<=q;i++)
    {
        int u, v;
        cin>>u>>v;
        int rootu = findroot(u);
        int rootv = findroot(v);
        if (rootu==rootv || child[rootv].find(u) != child[rootv].end()) // 2 dinh da thuoc cung mot thanh phan lien thong
        {
            cout<<ans<<endl;
            continue;
        }
        child[rootv].insert(u);
        ans += numb[rootv];
        // khi ta noi 1 canh co huong tu u den tplt v thi ta se them duoc so luong dinh 
        // trong tplt v
        add(rootu, rootv);
        while(!store.empty())
        {
            pair<int,int> edge = store.back();
            store.pop_back();
            unite(findroot(edge.first), findroot(edge.second));
        }
        cout<<ans<<endl;
    }

    return 0;
}

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