oj.uz

Submission #173437

# Submission time Handle Problem Language Result Execution time Memory
173437 2020-01-04T06:19:12 Z easrui 우호 조약 체결 (JOI14_friends) C++14
0 / 100
 290 ms 12636 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)
{
    ch[s] = 1;
    int p = 0;
    for(int e : G[s]){
        if(p) join(e,p);
        p = e;
    }
    for(int e : G[s]) if(!ch[e]) act(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 i=1; i<=N; i++) if(!ch[i]) act(i);
    for(int i=1; i<=N; i++){
        if(fnd(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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5068 KB Output is correct
4 Incorrect 7 ms 5112 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 5496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 8152 KB Output is correct
2 Incorrect 290 ms 12636 KB Output isn't correct
3 Halted 0 ms 0 KB -