답안 #42428 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
42428	2018-02-27T06:09:02 Z	dqhungdl	우호 조약 체결 (JOI14_friends)	C++14	100 / 100	121 ms	69420 KB

friends

#include <bits/stdc++.h>
using namespace std;

int64_t n,m,res=0,P[100005],Size[100005];
bool Free[100005];
vector<int64_t> V,g[100005];

int64_t Find(int64_t u)
{
    if(u==P[u])
        return u;
    return P[u]=Find(P[u]);
}

void Union(int64_t u,int64_t v)
{
    if(Size[u]<Size[v])
        swap(u,v);
    P[v]=u;
    Size[u]+=Size[v];
}

void DFS(int64_t u)
{
    for(int64_t i=0;i<g[u].size();i++)
    {
        V.push_back(g[u][i]);
        if(Free[g[u][i]]==false)
        {
            Free[g[u][i]]=true;
            DFS(g[u][i]);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>n>>m;
    int64_t u,v;
    while(m--)
    {
        cin>>u>>v;
        g[u].push_back(v);
    }
    for(int64_t i=1;i<=n;i++)
    {
        P[i]=i;
        Size[i]=1;
    }
    for(int64_t i=1;i<=n;i++)
        if(Free[i]==false&&g[i].size()>=2)
        {
            V.clear();
            DFS(i);
            for(int64_t j=1;j<V.size();j++)
            {
                int64_t u=Find(V[0]);
                int64_t v=Find(V[j]);
                if(u!=v)
                    Union(u,v);
            }
        }
    for(int64_t i=1;i<=n;i++)
        if(P[i]==i)
        {
            if(Size[i]>1)
                res+=Size[i]*(Size[i]-1);
            else
                res+=g[i].size();
        }
    cout<<res;
}

Compilation message

friends.cpp: In function 'void DFS(int64_t)':
friends.cpp:25:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<g[u].size();i++)
                      ^
friends.cpp: In function 'int main()':
friends.cpp:57:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int64_t j=1;j<V.size();j++)
                              ^

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2680 KB	Output is correct
2	Correct	3 ms	2784 KB	Output is correct
3	Correct	3 ms	2784 KB	Output is correct
4	Correct	3 ms	2784 KB	Output is correct
5	Correct	4 ms	2784 KB	Output is correct
6	Correct	3 ms	2796 KB	Output is correct
7	Correct	4 ms	2800 KB	Output is correct
8	Correct	4 ms	2944 KB	Output is correct
9	Correct	5 ms	2944 KB	Output is correct
10	Correct	4 ms	2944 KB	Output is correct
11	Correct	4 ms	2952 KB	Output is correct
12	Correct	3 ms	2952 KB	Output is correct
13	Correct	3 ms	2952 KB	Output is correct
14	Correct	4 ms	2952 KB	Output is correct
15	Correct	3 ms	2952 KB	Output is correct
16	Correct	4 ms	2952 KB	Output is correct
17	Correct	3 ms	2952 KB	Output is correct
18	Correct	3 ms	2960 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	3252 KB	Output is correct
2	Correct	4 ms	3252 KB	Output is correct
3	Correct	11 ms	4164 KB	Output is correct
4	Correct	46 ms	8840 KB	Output is correct
5	Correct	34 ms	8840 KB	Output is correct
6	Correct	64 ms	12660 KB	Output is correct
7	Correct	4 ms	12660 KB	Output is correct
8	Correct	8 ms	12660 KB	Output is correct
9	Correct	10 ms	12660 KB	Output is correct
10	Correct	24 ms	12660 KB	Output is correct
11	Correct	71 ms	15532 KB	Output is correct
12	Correct	8 ms	15532 KB	Output is correct
13	Correct	6 ms	15532 KB	Output is correct
14	Correct	6 ms	15532 KB	Output is correct
15	Correct	9 ms	15532 KB	Output is correct
16	Correct	12 ms	15532 KB	Output is correct
17	Correct	55 ms	17616 KB	Output is correct
18	Correct	5 ms	17616 KB	Output is correct
19	Correct	5 ms	17616 KB	Output is correct
20	Correct	60 ms	19852 KB	Output is correct
21	Correct	5 ms	19852 KB	Output is correct
22	Correct	5 ms	19852 KB	Output is correct
23	Correct	7 ms	19852 KB	Output is correct
24	Correct	6 ms	19852 KB	Output is correct
25	Correct	5 ms	19852 KB	Output is correct
26	Correct	5 ms	19852 KB	Output is correct
27	Correct	5 ms	19852 KB	Output is correct
28	Correct	5 ms	19852 KB	Output is correct

Subtask #3
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	55 ms	19852 KB	Output is correct
2	Correct	96 ms	23304 KB	Output is correct
3	Correct	113 ms	25616 KB	Output is correct
4	Correct	57 ms	25616 KB	Output is correct
5	Correct	24 ms	25616 KB	Output is correct
6	Correct	84 ms	28332 KB	Output is correct
7	Correct	74 ms	29348 KB	Output is correct
8	Correct	72 ms	31380 KB	Output is correct
9	Correct	52 ms	31380 KB	Output is correct
10	Correct	85 ms	33884 KB	Output is correct
11	Correct	102 ms	39760 KB	Output is correct
12	Correct	121 ms	41948 KB	Output is correct
13	Correct	39 ms	41948 KB	Output is correct
14	Correct	65 ms	42340 KB	Output is correct
15	Correct	22 ms	42340 KB	Output is correct
16	Correct	6 ms	42340 KB	Output is correct
17	Correct	5 ms	42340 KB	Output is correct
18	Correct	108 ms	47352 KB	Output is correct
19	Correct	97 ms	49624 KB	Output is correct
20	Correct	61 ms	49624 KB	Output is correct
21	Correct	27 ms	49624 KB	Output is correct
22	Correct	7 ms	49624 KB	Output is correct
23	Correct	30 ms	49624 KB	Output is correct
24	Correct	55 ms	50392 KB	Output is correct
25	Correct	38 ms	51960 KB	Output is correct
26	Correct	53 ms	57196 KB	Output is correct
27	Correct	104 ms	59928 KB	Output is correct
28	Correct	46 ms	59928 KB	Output is correct
29	Correct	54 ms	59928 KB	Output is correct
30	Correct	104 ms	63504 KB	Output is correct
31	Correct	43 ms	63504 KB	Output is correct
32	Correct	37 ms	63504 KB	Output is correct
33	Correct	41 ms	63504 KB	Output is correct
34	Correct	49 ms	63700 KB	Output is correct
35	Correct	36 ms	65736 KB	Output is correct
36	Correct	50 ms	69420 KB	Output is correct
37	Correct	45 ms	69420 KB	Output is correct

답안 #42428

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