Submission #58537

#	Time	Username	Problem	Language	Result	Execution time	Memory
58537		leehosu01	우호 조약 체결 (JOI14_friends)	C++17	0 / 100	61 ms	1708 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(F(X)!=F(Y))
        {
            P[P[X]]=P[Y];
  //          puts("ABA");
            from[Y].insert(from[Y].end(),from[X].begin(),from[X].end());
  //          puts("AMA");
            from[X].clear();
   //         puts("AEA");
            return 1;
        }
        return 0;
    }
};
vector<vector<int> >V;
vector<int>ST,NST,VC;
bitset<100000>ch,IS;
int N,M;
int main()
{
   // freopen("in.txt","r",stdin);
    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++)
        if(V[i].size()>=2)
        {
            for(auto&I:V[i])tr.ch(I,V[i][0]),IS.set(I);
            ch.set(i);
        }
    for(int i=0;i<N;i++)
    {
  //      printf("A");
        if(V[i].size()==1&&IS.test(i))
            ST.push_back(i);
 //       printf("B");
    }
    while(ST.size())
    {
        NST.resize(0);
  //      puts("AA");
        for(auto&J:ST)for(auto&I:V[J])
        {
  //          puts("BC");
            if(V[I].size()<=1)
            {
                if(!IS.test(I))NST.push_back(I);
                tr.ch(I,J),IS.set(I);
            }
            else if(V[I].size()>1&&tr.ch(I,J))
            {
                IS.set(I);
                tr.ch(I,*tr.from[tr.F(I)].begin());
                tr.ch(V[I][0],*tr.from[tr.F(I)].begin());
            }
        }
   //     puts("BB");
        swap(ST,NST);
    }
    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+=VC[tr.P[i]]*(VC[tr.P[i]]-1);
    cout<<tot<<'\n';
    for(int i=0;i<N;i++)if(IS.test(i)==0)tot+=V[i].size();
    cout<<tot;
    return 0;
}

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