oj.uz

Submission #173444

# Submission time Handle Problem Language Result Execution time Memory
173444 2020-01-04T06:30:48 Z easrui 우호 조약 체결 (JOI14_friends) C++14
5 / 100
 1000 ms 6264 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<=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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 10 ms 5112 KB Output is correct
9 Correct 7 ms 4984 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 5036 KB Output is correct
13 Correct 6 ms 5112 KB Output is correct
14 Correct 6 ms 4984 KB Output is correct
15 Correct 6 ms 4984 KB Output is correct
16 Correct 6 ms 5112 KB Output is correct
17 Correct 6 ms 5112 KB Output is correct
18 Correct 6 ms 4984 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 5240 KB Output is correct
2 Correct 270 ms 5496 KB Output is correct
3 Execution timed out 1079 ms 5496 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 6264 KB Time limit exceeded
2 Halted 0 ms 0 KB -