Submission #58702

#	Time	Username	Problem	Language	Result	Execution time	Memory
58702		leehosu01	우호 조약 체결 (JOI14_friends)	C++17	100 / 100	215 ms	77504 KiB

friends

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
class UN{
public:
    vector<int>P;
    vector<list<int> >from;
    UN(int n){P.resize(n);from.resize(n);for(int i=0;i<n;i++)P[i]=i,from[i].push_back(i);}
    int F(int X){return X==P[X]?X:P[X]=F(P[X]);}
    bool ch(int X,int Y)
    {
        if(from[F(X)].size()>from[F(Y)].size())swap(X,Y);
        if(F(X)!=F(Y))
        {
            P[P[X]]=P[Y];
            from[Y].insert(from[Y].end(),from[X].begin(),from[X].end());
            from[X].clear();
            return 1;
        }
        return 0;
    }
};
vector<vector<int> >V;
vector<int>ST,NST,VC;
bitset<100000>IS,ch;
int N,M;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>M;
    UN tr(N);
    V.resize(N);
    VC.resize(N);
    for(int i=0;i<M;i++)
    {
        int T,O;
        cin>>T>>O;T--,O--;
        V[T].push_back(O);
    }
    for(int i=0;i<N;i++)ST.push_back(i),ch.set(i);
    while(!ST.empty())
    {
        ch.reset();
        for(auto&I:ST)
        {
            if(IS.test(I))for(auto&J:V[I])
            {
                tr.ch(J,I);
                if(IS.test(J)==0&&ch.test(J)==0)
                {
                    NST.push_back(J);
                    ch.set(J);
                }IS.set(J);
            }
            else if(V[I].size()>=2)for(auto&J:V[I])
            {
                tr.ch(J,V[I][0]);
                if(IS.test(J)==0&&ch.test(J)==0)
                {
                    NST.push_back(J);
                    ch.set(J);
                }IS.set(J);
            }

        }
        swap(ST,NST);
        NST.resize(0);
    }
    for(int i=0;i<N;i++)VC[tr.F(i)]++;
    ll tot=0;
    for(int i=0;i<N;i++)if(tr.F(i)==i)tot+=(ll)VC[tr.P[i]]*(VC[tr.P[i]]-1);
    for(int i=0;i<N;i++)if(IS.test(i)==0)tot+=V[i].size();
    cout<<tot;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65