oj.uz

답안 #173448

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
173448 2020-01-04T06:32:35 Z easrui 우호 조약 체결 (JOI14_friends) C++14
100 / 100
 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;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 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

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 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

Subtask #3
65.0 / 65.0

# 결과 실행 시간 메모리 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