| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 173448 |
2020-01-04T06:32:35 Z |
easrui |
우호 조약 체결 (JOI14_friends) |
C++14 |
|
760 ms |
12252 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN = 2e5+5;
int N,M,s,e,D[MN],cur,par[MN];
ll sz[MN],ans;
vector<int> G[MN];
bool ch[MN];
int fnd(int s)
{
return par[s]==s ? s : par[s]=fnd(par[s]);
}
void join(int x, int y)
{
x = fnd(x), y = fnd(y);
if(x==y) return;
par[y] = x;
sz[x] += sz[y];
}
void act(int s)
{
int p = 0;
if(sz[fnd(s)]>1) p = s;
for(int e : G[s]){
if(p) join(e,p);
p = e;
}
}
int main()
{
cin >> N >> M;
for(int i=1; i<=N; i++) par[i] = i, sz[i] = 1;
for(int i=0; i<M; i++){
cin >> s >> e;
G[s].push_back(e);
D[s]++;
if(D[s]>D[cur]) cur = s;
}
for(int j=1; j<=100; j++)
for(int i=1; i<=N; i++) act(i);
for(int i=1; i<=N; i++){
if(par[i]==i) ans += sz[i]*(sz[i]-1);
for(int e : G[i]) if(fnd(i)!=fnd(e)) ans++;
}
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 5 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 6 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 7 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 8 |
Correct |
10 ms |
5112 KB |
Output is correct |
| 9 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 10 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 11 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 12 |
Correct |
6 ms |
5024 KB |
Output is correct |
| 13 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 14 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 15 |
Correct |
7 ms |
5084 KB |
Output is correct |
| 16 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 17 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 18 |
Correct |
6 ms |
5084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
5240 KB |
Output is correct |
| 2 |
Correct |
13 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
50 ms |
5384 KB |
Output is correct |
| 4 |
Correct |
263 ms |
7512 KB |
Output is correct |
| 5 |
Correct |
209 ms |
7032 KB |
Output is correct |
| 6 |
Correct |
360 ms |
8568 KB |
Output is correct |
| 7 |
Correct |
11 ms |
5112 KB |
Output is correct |
| 8 |
Correct |
27 ms |
5280 KB |
Output is correct |
| 9 |
Correct |
59 ms |
5496 KB |
Output is correct |
| 10 |
Correct |
103 ms |
6008 KB |
Output is correct |
| 11 |
Correct |
365 ms |
8568 KB |
Output is correct |
| 12 |
Correct |
39 ms |
5372 KB |
Output is correct |
| 13 |
Correct |
22 ms |
5240 KB |
Output is correct |
| 14 |
Correct |
21 ms |
5240 KB |
Output is correct |
| 15 |
Correct |
32 ms |
5368 KB |
Output is correct |
| 16 |
Correct |
71 ms |
5752 KB |
Output is correct |
| 17 |
Correct |
362 ms |
8460 KB |
Output is correct |
| 18 |
Correct |
14 ms |
5240 KB |
Output is correct |
| 19 |
Correct |
18 ms |
5368 KB |
Output is correct |
| 20 |
Correct |
358 ms |
8552 KB |
Output is correct |
| 21 |
Correct |
20 ms |
5240 KB |
Output is correct |
| 22 |
Correct |
20 ms |
5240 KB |
Output is correct |
| 23 |
Correct |
31 ms |
5308 KB |
Output is correct |
| 24 |
Correct |
22 ms |
5240 KB |
Output is correct |
| 25 |
Correct |
14 ms |
5372 KB |
Output is correct |
| 26 |
Correct |
20 ms |
5240 KB |
Output is correct |
| 27 |
Correct |
14 ms |
5368 KB |
Output is correct |
| 28 |
Correct |
20 ms |
5240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
345 ms |
6252 KB |
Output is correct |
| 2 |
Correct |
690 ms |
9424 KB |
Output is correct |
| 3 |
Correct |
760 ms |
11820 KB |
Output is correct |
| 4 |
Correct |
433 ms |
9784 KB |
Output is correct |
| 5 |
Correct |
249 ms |
8440 KB |
Output is correct |
| 6 |
Correct |
557 ms |
10008 KB |
Output is correct |
| 7 |
Correct |
558 ms |
11696 KB |
Output is correct |
| 8 |
Correct |
537 ms |
11640 KB |
Output is correct |
| 9 |
Correct |
385 ms |
9976 KB |
Output is correct |
| 10 |
Correct |
467 ms |
10744 KB |
Output is correct |
| 11 |
Correct |
733 ms |
12004 KB |
Output is correct |
| 12 |
Correct |
673 ms |
12152 KB |
Output is correct |
| 13 |
Correct |
191 ms |
10872 KB |
Output is correct |
| 14 |
Correct |
380 ms |
8704 KB |
Output is correct |
| 15 |
Correct |
237 ms |
8568 KB |
Output is correct |
| 16 |
Correct |
59 ms |
6648 KB |
Output is correct |
| 17 |
Correct |
52 ms |
6136 KB |
Output is correct |
| 18 |
Correct |
697 ms |
11372 KB |
Output is correct |
| 19 |
Correct |
699 ms |
11512 KB |
Output is correct |
| 20 |
Correct |
451 ms |
9428 KB |
Output is correct |
| 21 |
Correct |
247 ms |
8312 KB |
Output is correct |
| 22 |
Correct |
55 ms |
6776 KB |
Output is correct |
| 23 |
Correct |
189 ms |
6872 KB |
Output is correct |
| 24 |
Correct |
460 ms |
9492 KB |
Output is correct |
| 25 |
Correct |
196 ms |
10912 KB |
Output is correct |
| 26 |
Correct |
417 ms |
11896 KB |
Output is correct |
| 27 |
Correct |
652 ms |
12252 KB |
Output is correct |
| 28 |
Correct |
421 ms |
10284 KB |
Output is correct |
| 29 |
Correct |
419 ms |
10204 KB |
Output is correct |
| 30 |
Correct |
650 ms |
11860 KB |
Output is correct |
| 31 |
Correct |
391 ms |
9336 KB |
Output is correct |
| 32 |
Correct |
191 ms |
11000 KB |
Output is correct |
| 33 |
Correct |
188 ms |
10872 KB |
Output is correct |
| 34 |
Correct |
384 ms |
9912 KB |
Output is correct |
| 35 |
Correct |
191 ms |
10872 KB |
Output is correct |
| 36 |
Correct |
346 ms |
11492 KB |
Output is correct |
| 37 |
Correct |
460 ms |
10232 KB |
Output is correct |
