oj.uz

Submission #156085

# Submission time Handle Problem Language Result Execution time Memory
156085 2019-10-03T08:18:22 Z atoiz 우호 조약 체결 (JOI14_friends) C++14
0 / 100
 100 ms 9472 KB 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100007;

int n, m;
vector<int> gr[MAXN];
bool vis[MAXN];

int dsu[MAXN], sz[MAXN];
void init(int n) { for (int i = 0; i < n; ++i) dsu[i] = i, sz[i] = 1; }
int get(int i) { return (i == dsu[i] ? i : dsu[i] = get(dsu[i])); }
bool same(int i, int j) { return get(i) == get(j); }
void join(int i, int j) { i = get(i), j = get(j); if (i == j) return; if (sz[i] < sz[j]) swap(i, j); sz[i] += sz[j], dsu[j] = i; }

void dfs(int);
void add(int u, int v)
{
    bool redfs = (!vis[v] || sz[get(v)] == 1);
    join(u, v);
    if (redfs) dfs(v);
}
void dfs(int u)
{
    vis[u] = 1;
    if (sz[get(u)] > 1) for (int v : gr[u]) add(u, v);
    else if ((int) gr[u].size() == 1) {
        if (!vis[gr[u][0]]) dfs(gr[u][0]);
    } else if (gr[u].empty()) {}
    else {
        add(gr[u].back(), gr[u].front());
        for (int v : gr[u]) if (v != gr[u].front()) add(gr[u].front(), v);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        gr[u].push_back(v);
    }
    init(n + 1);
    for (int u = 1; u <= n; ++u) if (!vis[u]) dfs(u);

    long long ans = 0;
    for (int u = 1; u <= n; ++u) for (int v : gr[u]) {
        if (!same(u, v)) ++ans;
    }
    for (int u = 1; u <= n; ++u) if (u == get(u)) ans += 1ll * sz[u] * (sz[u] - 1);
    cout << ans << endl;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 5648 KB Output is correct
2 Incorrect 100 ms 9472 KB Output isn't correct
3 Halted 0 ms 0 KB -