답안 #58703 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58703	2018-07-18T23:19:33 Z	leehosu01	우호 조약 체결 (JOI14_friends)	C++17	100 / 100	143 ms	8076 KB

friends

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
class UN{
public:
    vector<int>P;
    UN(int n){P.resize(n);for(int i=0;i<n;i++)P[i]=i;}
    int F(int X){return X==P[X]?X:P[X]=F(P[X]);}
    void ch(int X,int Y)
    {
        if(F(X)!=F(Y))
            P[P[X]]=P[Y];
    }
};
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.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	3 ms	504 KB	Output is correct
5	Correct	2 ms	504 KB	Output is correct
6	Correct	3 ms	504 KB	Output is correct
7	Correct	2 ms	504 KB	Output is correct
8	Correct	3 ms	508 KB	Output is correct
9	Correct	2 ms	508 KB	Output is correct
10	Correct	2 ms	508 KB	Output is correct
11	Correct	2 ms	508 KB	Output is correct
12	Correct	3 ms	508 KB	Output is correct
13	Correct	3 ms	508 KB	Output is correct
14	Correct	3 ms	508 KB	Output is correct
15	Correct	3 ms	508 KB	Output is correct
16	Correct	3 ms	508 KB	Output is correct
17	Correct	3 ms	508 KB	Output is correct
18	Correct	2 ms	508 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	748 KB	Output is correct
2	Correct	4 ms	756 KB	Output is correct
3	Correct	10 ms	1088 KB	Output is correct
4	Correct	45 ms	1772 KB	Output is correct
5	Correct	38 ms	1772 KB	Output is correct
6	Correct	69 ms	2284 KB	Output is correct
7	Correct	3 ms	2284 KB	Output is correct
8	Correct	5 ms	2284 KB	Output is correct
9	Correct	9 ms	2284 KB	Output is correct
10	Correct	17 ms	2284 KB	Output is correct
11	Correct	61 ms	2284 KB	Output is correct
12	Correct	9 ms	2284 KB	Output is correct
13	Correct	5 ms	2284 KB	Output is correct
14	Correct	6 ms	2284 KB	Output is correct
15	Correct	8 ms	2284 KB	Output is correct
16	Correct	13 ms	2284 KB	Output is correct
17	Correct	50 ms	2284 KB	Output is correct
18	Correct	4 ms	2284 KB	Output is correct
19	Correct	4 ms	2284 KB	Output is correct
20	Correct	64 ms	2300 KB	Output is correct
21	Correct	5 ms	2300 KB	Output is correct
22	Correct	4 ms	2300 KB	Output is correct
23	Correct	7 ms	2300 KB	Output is correct
24	Correct	4 ms	2300 KB	Output is correct
25	Correct	4 ms	2300 KB	Output is correct
26	Correct	5 ms	2300 KB	Output is correct
27	Correct	5 ms	2300 KB	Output is correct
28	Correct	4 ms	2300 KB	Output is correct

Subtask #3
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	51 ms	2300 KB	Output is correct
2	Correct	127 ms	7848 KB	Output is correct
3	Correct	139 ms	7848 KB	Output is correct
4	Correct	71 ms	7848 KB	Output is correct
5	Correct	35 ms	7848 KB	Output is correct
6	Correct	105 ms	7848 KB	Output is correct
7	Correct	83 ms	7848 KB	Output is correct
8	Correct	84 ms	7848 KB	Output is correct
9	Correct	88 ms	7848 KB	Output is correct
10	Correct	75 ms	7848 KB	Output is correct
11	Correct	134 ms	7848 KB	Output is correct
12	Correct	132 ms	8052 KB	Output is correct
13	Correct	48 ms	8052 KB	Output is correct
14	Correct	68 ms	8052 KB	Output is correct
15	Correct	31 ms	8052 KB	Output is correct
16	Correct	8 ms	8052 KB	Output is correct
17	Correct	7 ms	8052 KB	Output is correct
18	Correct	128 ms	8052 KB	Output is correct
19	Correct	143 ms	8052 KB	Output is correct
20	Correct	96 ms	8052 KB	Output is correct
21	Correct	34 ms	8052 KB	Output is correct
22	Correct	7 ms	8052 KB	Output is correct
23	Correct	43 ms	8052 KB	Output is correct
24	Correct	59 ms	8052 KB	Output is correct
25	Correct	44 ms	8052 KB	Output is correct
26	Correct	64 ms	8052 KB	Output is correct
27	Correct	115 ms	8076 KB	Output is correct
28	Correct	60 ms	8076 KB	Output is correct
29	Correct	63 ms	8076 KB	Output is correct
30	Correct	140 ms	8076 KB	Output is correct
31	Correct	52 ms	8076 KB	Output is correct
32	Correct	55 ms	8076 KB	Output is correct
33	Correct	56 ms	8076 KB	Output is correct
34	Correct	61 ms	8076 KB	Output is correct
35	Correct	51 ms	8076 KB	Output is correct
36	Correct	65 ms	8076 KB	Output is correct
37	Correct	58 ms	8076 KB	Output is correct

답안 #58703

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 30.0 / 30.0

Subtask #3 65.0 / 65.0

Subtask #1
5.0 / 5.0

Subtask #2
30.0 / 30.0

Subtask #3
65.0 / 65.0