oj.uz

답안 #422602

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
422602 2021-06-10T08:59:49 Z Hideo 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
100 / 100
 1477 ms 79732 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define pi pair < int, int >

const int N = 3e5 + 7;
const int INF = 1e9 + 7;

ll sum;
ll p[N];
int n, m;

set < int > g[N], q[N];

int findp (int x){
    if (p[x] < 0)
        return x;
    return p[x] = findp(p[x]);
}

bool check (int v, int u){
    v = findp(v);
    u = findp(u);
    if (v != u){
        for (auto to : g[u])
            if (findp(to) == v)
                return true;
    }
    return false;
}

void unite (int v, int u){
    v = findp(v);
    u = findp(u);
    if (v != u){
        sum -= 1ll * int(g[u].size()) * -p[u];
        sum -= 1ll * int(g[v].size()) * -p[v];
        if (g[u].size() > g[v].size())
            swap(v, u);
        for (auto to : g[u]){
            g[v].insert(to);
            q[findp(to)].erase(u);
            q[findp(to)].insert(v);
        }
        for (auto to : q[u]){
            q[v].insert(to);
        }
        g[v].insert(u);
        g[v].erase(v);
        p[v] += p[u];
        p[u] = v;
        sum += 1ll * int(g[v].size()) * -p[v];
//        cout << v << ' ' << u << endl;
        vector < int > go;
        for (auto to : g[u]){
            if (q[v].find(findp(to)) != q[v].end()){
                go.pb(to);
            }
        }
        for (auto to : q[u]){
            if (q[to].find(v) != q[to].end()){
                go.pb(to);
            }
        }
        for (int to : go){
            unite(v, to);
        }
    }
}

main (){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(p, -1, sizeof(p));
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int a, b;
        cin >> a >> b;
        if (q[findp(b)].find(findp(a)) != q[findp(b)].end())
            unite(a, b);
        else {
            b = findp(b);
            sum -= 1ll * int(g[b].size()) * -p[b];
            g[b].insert(a);
            g[b].erase(b);
            a = findp(a);
            q[a].insert(b);
            sum += 1ll * int(g[b].size()) * -p[b];
        }
        cout << sum << endl;
    }
}

Compilation message

joitter2.cpp:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 | main (){
      | ^~~~

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 30796 KB Output is correct
2 Correct 19 ms 30796 KB Output is correct
3 Correct 18 ms 30732 KB Output is correct
4 Correct 18 ms 30796 KB Output is correct
5 Correct 21 ms 30840 KB Output is correct
6 Correct 20 ms 30824 KB Output is correct
7 Correct 26 ms 30960 KB Output is correct
8 Correct 23 ms 30856 KB Output is correct
9 Correct 25 ms 30888 KB Output is correct
10 Correct 20 ms 30796 KB Output is correct
11 Correct 18 ms 30800 KB Output is correct
12 Correct 19 ms 30736 KB Output is correct
13 Correct 19 ms 30796 KB Output is correct
14 Correct 22 ms 30804 KB Output is correct
15 Correct 17 ms 30832 KB Output is correct
16 Correct 17 ms 30792 KB Output is correct
17 Correct 18 ms 30800 KB Output is correct
18 Correct 17 ms 30764 KB Output is correct
19 Correct 17 ms 30792 KB Output is correct
20 Correct 20 ms 30796 KB Output is correct
21 Correct 21 ms 30796 KB Output is correct
22 Correct 18 ms 30848 KB Output is correct
23 Correct 24 ms 30792 KB Output is correct
24 Correct 19 ms 30840 KB Output is correct
25 Correct 22 ms 30840 KB Output is correct
26 Correct 19 ms 30840 KB Output is correct
27 Correct 20 ms 30796 KB Output is correct
28 Correct 19 ms 30844 KB Output is correct
29 Correct 20 ms 30844 KB Output is correct
30 Correct 21 ms 30728 KB Output is correct
31 Correct 23 ms 30748 KB Output is correct
32 Correct 20 ms 30788 KB Output is correct
33 Correct 21 ms 30764 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 30796 KB Output is correct
2 Correct 19 ms 30796 KB Output is correct
3 Correct 18 ms 30732 KB Output is correct
4 Correct 18 ms 30796 KB Output is correct
5 Correct 21 ms 30840 KB Output is correct
6 Correct 20 ms 30824 KB Output is correct
7 Correct 26 ms 30960 KB Output is correct
8 Correct 23 ms 30856 KB Output is correct
9 Correct 25 ms 30888 KB Output is correct
10 Correct 20 ms 30796 KB Output is correct
11 Correct 18 ms 30800 KB Output is correct
12 Correct 19 ms 30736 KB Output is correct
13 Correct 19 ms 30796 KB Output is correct
14 Correct 22 ms 30804 KB Output is correct
15 Correct 17 ms 30832 KB Output is correct
16 Correct 17 ms 30792 KB Output is correct
17 Correct 18 ms 30800 KB Output is correct
18 Correct 17 ms 30764 KB Output is correct
19 Correct 17 ms 30792 KB Output is correct
20 Correct 20 ms 30796 KB Output is correct
21 Correct 21 ms 30796 KB Output is correct
22 Correct 18 ms 30848 KB Output is correct
23 Correct 24 ms 30792 KB Output is correct
24 Correct 19 ms 30840 KB Output is correct
25 Correct 22 ms 30840 KB Output is correct
26 Correct 19 ms 30840 KB Output is correct
27 Correct 20 ms 30796 KB Output is correct
28 Correct 19 ms 30844 KB Output is correct
29 Correct 20 ms 30844 KB Output is correct
30 Correct 21 ms 30728 KB Output is correct
31 Correct 23 ms 30748 KB Output is correct
32 Correct 20 ms 30788 KB Output is correct
33 Correct 21 ms 30764 KB Output is correct
34 Correct 40 ms 30956 KB Output is correct
35 Correct 584 ms 34836 KB Output is correct
36 Correct 626 ms 36644 KB Output is correct
37 Correct 621 ms 36724 KB Output is correct
38 Correct 658 ms 36536 KB Output is correct
39 Correct 30 ms 31052 KB Output is correct
40 Correct 28 ms 31352 KB Output is correct
41 Correct 31 ms 31364 KB Output is correct
42 Correct 26 ms 31044 KB Output is correct
43 Correct 27 ms 31080 KB Output is correct
44 Correct 30 ms 31044 KB Output is correct
45 Correct 28 ms 31092 KB Output is correct
46 Correct 28 ms 30976 KB Output is correct
47 Correct 28 ms 31176 KB Output is correct
48 Correct 29 ms 31248 KB Output is correct
49 Correct 48 ms 31804 KB Output is correct
50 Correct 672 ms 36848 KB Output is correct
51 Correct 40 ms 31312 KB Output is correct
52 Correct 649 ms 35584 KB Output is correct
53 Correct 45 ms 31728 KB Output is correct
54 Correct 622 ms 36144 KB Output is correct
55 Correct 28 ms 31308 KB Output is correct
56 Correct 32 ms 31332 KB Output is correct
57 Correct 29 ms 31612 KB Output is correct
58 Correct 35 ms 31612 KB Output is correct
59 Correct 34 ms 31444 KB Output is correct
60 Correct 596 ms 34604 KB Output is correct
61 Correct 32 ms 31180 KB Output is correct
62 Correct 664 ms 36316 KB Output is correct

Subtask #3
83.0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 30796 KB Output is correct
2 Correct 19 ms 30796 KB Output is correct
3 Correct 18 ms 30732 KB Output is correct
4 Correct 18 ms 30796 KB Output is correct
5 Correct 21 ms 30840 KB Output is correct
6 Correct 20 ms 30824 KB Output is correct
7 Correct 26 ms 30960 KB Output is correct
8 Correct 23 ms 30856 KB Output is correct
9 Correct 25 ms 30888 KB Output is correct
10 Correct 20 ms 30796 KB Output is correct
11 Correct 18 ms 30800 KB Output is correct
12 Correct 19 ms 30736 KB Output is correct
13 Correct 19 ms 30796 KB Output is correct
14 Correct 22 ms 30804 KB Output is correct
15 Correct 17 ms 30832 KB Output is correct
16 Correct 17 ms 30792 KB Output is correct
17 Correct 18 ms 30800 KB Output is correct
18 Correct 17 ms 30764 KB Output is correct
19 Correct 17 ms 30792 KB Output is correct
20 Correct 20 ms 30796 KB Output is correct
21 Correct 21 ms 30796 KB Output is correct
22 Correct 18 ms 30848 KB Output is correct
23 Correct 24 ms 30792 KB Output is correct
24 Correct 19 ms 30840 KB Output is correct
25 Correct 22 ms 30840 KB Output is correct
26 Correct 19 ms 30840 KB Output is correct
27 Correct 20 ms 30796 KB Output is correct
28 Correct 19 ms 30844 KB Output is correct
29 Correct 20 ms 30844 KB Output is correct
30 Correct 21 ms 30728 KB Output is correct
31 Correct 23 ms 30748 KB Output is correct
32 Correct 20 ms 30788 KB Output is correct
33 Correct 21 ms 30764 KB Output is correct
34 Correct 40 ms 30956 KB Output is correct
35 Correct 584 ms 34836 KB Output is correct
36 Correct 626 ms 36644 KB Output is correct
37 Correct 621 ms 36724 KB Output is correct
38 Correct 658 ms 36536 KB Output is correct
39 Correct 30 ms 31052 KB Output is correct
40 Correct 28 ms 31352 KB Output is correct
41 Correct 31 ms 31364 KB Output is correct
42 Correct 26 ms 31044 KB Output is correct
43 Correct 27 ms 31080 KB Output is correct
44 Correct 30 ms 31044 KB Output is correct
45 Correct 28 ms 31092 KB Output is correct
46 Correct 28 ms 30976 KB Output is correct
47 Correct 28 ms 31176 KB Output is correct
48 Correct 29 ms 31248 KB Output is correct
49 Correct 48 ms 31804 KB Output is correct
50 Correct 672 ms 36848 KB Output is correct
51 Correct 40 ms 31312 KB Output is correct
52 Correct 649 ms 35584 KB Output is correct
53 Correct 45 ms 31728 KB Output is correct
54 Correct 622 ms 36144 KB Output is correct
55 Correct 28 ms 31308 KB Output is correct
56 Correct 32 ms 31332 KB Output is correct
57 Correct 29 ms 31612 KB Output is correct
58 Correct 35 ms 31612 KB Output is correct
59 Correct 34 ms 31444 KB Output is correct
60 Correct 596 ms 34604 KB Output is correct
61 Correct 32 ms 31180 KB Output is correct
62 Correct 664 ms 36316 KB Output is correct
63 Correct 987 ms 61692 KB Output is correct
64 Correct 935 ms 61744 KB Output is correct
65 Correct 908 ms 61796 KB Output is correct
66 Correct 636 ms 44560 KB Output is correct
67 Correct 869 ms 71764 KB Output is correct
68 Correct 599 ms 44612 KB Output is correct
69 Correct 772 ms 44524 KB Output is correct
70 Correct 603 ms 44736 KB Output is correct
71 Correct 641 ms 44580 KB Output is correct
72 Correct 830 ms 55536 KB Output is correct
73 Correct 813 ms 57168 KB Output is correct
74 Correct 1477 ms 74588 KB Output is correct
75 Correct 1142 ms 50712 KB Output is correct
76 Correct 1231 ms 61332 KB Output is correct
77 Correct 1214 ms 61508 KB Output is correct
78 Correct 560 ms 45820 KB Output is correct
79 Correct 1052 ms 51804 KB Output is correct
80 Correct 454 ms 45804 KB Output is correct
81 Correct 871 ms 50180 KB Output is correct
82 Correct 900 ms 57984 KB Output is correct
83 Correct 915 ms 57892 KB Output is correct
84 Correct 860 ms 76708 KB Output is correct
85 Correct 839 ms 76572 KB Output is correct
86 Correct 687 ms 77796 KB Output is correct
87 Correct 964 ms 79732 KB Output is correct
88 Correct 811 ms 56496 KB Output is correct
89 Correct 1224 ms 59760 KB Output is correct