oj.uz

Submission #43169

# Submission time Handle Problem Language Result Execution time Memory
43169 2018-03-09T17:12:55 Z nickyrio 우호 조약 체결 (JOI14_friends) C++14
0 / 100
 78 ms 27164 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define DEBUG(x) { cerr << #x << '=' << x << endl; }
#define Arr(a, l, r) { cerr << #a << " = {"; FOR(_, l, r) cerr << ' ' << a[_]; cerr << "}\n"; }
#define N 1001000
#define pp pair<int, int>
#define endl '\n'
#define IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define taskname ""
#define bit(S, i) (((S) >> (i)) & 1)
using namespace std;

int visited[N], f[N], n;
vector<int> e[N];

int root(int u) { return f[u] < 0 ? u : (f[u] = root(f[u])); }
void Union(int a, int b){
    a = root(a), b = root(b);
    if (a == b) return;
    int t = f[a] + f[b];
    if (f[a] > f[b]) swap(a, b);
    f[a] = t;
    f[b] = a;    
}

int cnt;
void dfs(int u) {
    cnt++;
    DEBUG(u);
    visited[u] = 1;
    for (int v : e[u]) if (!visited[v]) {
        Union(u, v);
        dfs(v);
    }
}
int main() {
    #ifdef NERO
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    #endif //NERO
    IO;
    int m;
    cin >> n >> m;
    REP(i, m) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
    }
    FOR(u, 1, n) f[u] = -1;
    long long ans = 0;
    FOR(u, 1, n) if (!visited[u]) {
        cnt = 0;
        if (e[u].size() > 1) {
            int r = -1;
            for (int v : e[u]) {
                if (r != -1) Union(r, v);
                else r = v;
                dfs(v);
            }
        }
       // DEBUG(cnt);
    }
    //Arr(f, 1, n);
    FOR(u, 1, n) if (f[u] < 0) ans += 1ll * f[u] * (f[u] + 1);
    FOR(u, 1, n) {
        for (int v : e[u]) if (root(u) != root(v)) ans++;
    }
    cout << ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 21 ms 23928 KB Output is correct
3 Incorrect 20 ms 24112 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 65.0

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