oj.uz

답안 #173442

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
173442 2020-01-04T06:24:15 Z easrui 우호 조약 체결 (JOI14_friends) C++14
0 / 100
 1000 ms 6204 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[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<=N; 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
0 / 5.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1075 ms 6204 KB Time limit exceeded
2 Halted 0 ms 0 KB -