oj.uz

답안 #58532

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58532 2018-07-18T05:20:00 Z leehosu01 우호 조약 체결 (JOI14_friends) C++17
0 / 100
 173 ms 12264 KB 
#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);for(auto&K:tr.from[tr.F(I)])tr.ch(I,K),tr.ch(V[I][0],K);}
        }
   //     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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Incorrect 2 ms 488 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 1204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 2008 KB Output is correct
2 Incorrect 173 ms 12264 KB Output isn't correct
3 Halted 0 ms 0 KB -