답안 #43171 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43171	2018-03-09T17:28:41 Z	nickyrio	우호 조약 체결 (JOI14_friends)	C++14	100 / 100	151 ms	90684 KB

friends

#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;    
}

void dfs(int u) {
    visited[u] = 1;
    for (int v : e[u]) {
        Union(u, v);
        if (!visited[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]) {
        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
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	23800 KB	Output is correct
2	Correct	25 ms	23904 KB	Output is correct
3	Correct	24 ms	23904 KB	Output is correct
4	Correct	20 ms	23992 KB	Output is correct
5	Correct	20 ms	24144 KB	Output is correct
6	Correct	20 ms	24144 KB	Output is correct
7	Correct	23 ms	24144 KB	Output is correct
8	Correct	20 ms	24144 KB	Output is correct
9	Correct	22 ms	24144 KB	Output is correct
10	Correct	20 ms	24144 KB	Output is correct
11	Correct	19 ms	24148 KB	Output is correct
12	Correct	20 ms	24148 KB	Output is correct
13	Correct	19 ms	24260 KB	Output is correct
14	Correct	23 ms	24336 KB	Output is correct
15	Correct	23 ms	24336 KB	Output is correct
16	Correct	20 ms	24336 KB	Output is correct
17	Correct	19 ms	24336 KB	Output is correct
18	Correct	19 ms	24336 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	24348 KB	Output is correct
2	Correct	20 ms	24348 KB	Output is correct
3	Correct	32 ms	25024 KB	Output is correct
4	Correct	60 ms	27188 KB	Output is correct
5	Correct	47 ms	27932 KB	Output is correct
6	Correct	68 ms	30356 KB	Output is correct
7	Correct	20 ms	30356 KB	Output is correct
8	Correct	24 ms	30356 KB	Output is correct
9	Correct	27 ms	30356 KB	Output is correct
10	Correct	34 ms	30356 KB	Output is correct
11	Correct	70 ms	33164 KB	Output is correct
12	Correct	27 ms	33164 KB	Output is correct
13	Correct	25 ms	33164 KB	Output is correct
14	Correct	26 ms	33164 KB	Output is correct
15	Correct	25 ms	33164 KB	Output is correct
16	Correct	29 ms	33164 KB	Output is correct
17	Correct	67 ms	35400 KB	Output is correct
18	Correct	22 ms	35400 KB	Output is correct
19	Correct	24 ms	35400 KB	Output is correct
20	Correct	83 ms	37492 KB	Output is correct
21	Correct	21 ms	37492 KB	Output is correct
22	Correct	22 ms	37492 KB	Output is correct
23	Correct	30 ms	37492 KB	Output is correct
24	Correct	21 ms	37492 KB	Output is correct
25	Correct	26 ms	37492 KB	Output is correct
26	Correct	22 ms	37492 KB	Output is correct
27	Correct	21 ms	37492 KB	Output is correct
28	Correct	21 ms	37492 KB	Output is correct

Subtask #3
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	37636 KB	Output is correct
2	Correct	151 ms	43264 KB	Output is correct
3	Correct	151 ms	45440 KB	Output is correct
4	Correct	68 ms	45440 KB	Output is correct
5	Correct	51 ms	45440 KB	Output is correct
6	Correct	92 ms	48356 KB	Output is correct
7	Correct	90 ms	51124 KB	Output is correct
8	Correct	87 ms	53348 KB	Output is correct
9	Correct	61 ms	53736 KB	Output is correct
10	Correct	82 ms	55980 KB	Output is correct
11	Correct	108 ms	59500 KB	Output is correct
12	Correct	108 ms	62548 KB	Output is correct
13	Correct	61 ms	62548 KB	Output is correct
14	Correct	74 ms	62548 KB	Output is correct
15	Correct	46 ms	63268 KB	Output is correct
16	Correct	24 ms	63268 KB	Output is correct
17	Correct	22 ms	63268 KB	Output is correct
18	Correct	113 ms	67020 KB	Output is correct
19	Correct	112 ms	69340 KB	Output is correct
20	Correct	68 ms	69340 KB	Output is correct
21	Correct	43 ms	69340 KB	Output is correct
22	Correct	21 ms	69340 KB	Output is correct
23	Correct	58 ms	69340 KB	Output is correct
24	Correct	102 ms	72152 KB	Output is correct
25	Correct	54 ms	74480 KB	Output is correct
26	Correct	61 ms	79048 KB	Output is correct
27	Correct	125 ms	79976 KB	Output is correct
28	Correct	68 ms	79976 KB	Output is correct
29	Correct	75 ms	79976 KB	Output is correct
30	Correct	107 ms	83468 KB	Output is correct
31	Correct	59 ms	83468 KB	Output is correct
32	Correct	61 ms	84728 KB	Output is correct
33	Correct	60 ms	85868 KB	Output is correct
34	Correct	66 ms	86352 KB	Output is correct
35	Correct	61 ms	88216 KB	Output is correct
36	Correct	68 ms	90684 KB	Output is correct
37	Correct	73 ms	90684 KB	Output is correct

답안 #43171

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 30.0 / 30.0

Subtask #3 65.0 / 65.0

Subtask #1
5.0 / 5.0

Subtask #2
30.0 / 30.0

Subtask #3
65.0 / 65.0