답안 #269696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
269696	2020-08-17T08:40:08 Z	반딧불(#5114)	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	컴파일 오류	0 ms	0 KB

joitter2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
int par[100002]
ll sz[100002];
multiset<int> link[100002]; /// ���������� �͵��� �����̴�.
multiset<int> revLink[100002]; /// ������ �͵��� �����̴�.
set<int> coming[100002];
ll ans;

int find(int x){
    if(x==par[x]) return x;
    return par[x] = find(par[x]);
}

void init(){
    for(int i=1; i<=n; i++){
        par[i] = i;
        sz[i] = 1;
    }
}

int main(){
    scanf("%d %d", &n, &m);
    init();

    while(m--){
        int x, y;
        scanf("%d %d", &x, &y);
        int px = x;
        x = find(x), y = find(y); /// x -> y�� ���� ������ ��ġ�̴�.

        if(x==y){
            printf("%lld\n", ans);
            continue;
        }

        if(link[y].find(x) != link[y].end()){ /// �̹� ������ ���� ���, �� ���� �׷����� ��ģ��.
            ans += sz[x] * sz[y]; /// x->y�� ���� ��� �������� ���� ��� �Ѵ�.
            ans += sz[y] * sz[x]; /// y->x�� ���� ��� �������� ���� ��� �Ѵ�.
            ans -= sz[x] * ((ll)coming[x].size()) + sz[y] * ((ll)coming[y].size());
                                                                            /// �ϴ� indegree count�� ��� ���� ����. ���߿� �ٽ� ��ĥ ���̴�.

            set<int> st;
            for(auto nxt: coming[x]){
                if(par[nxt] != y) st.insert(nxt);
            }
            coming[x] = st;

            link[y].erase(x); /// �ڱ� ���η� ������ �־ ���� �� �����ϱ�...
            revLink[x].erase(y); /// �ڱ� ���η� ������ �־ ���� �� �����ϱ� 222222

            if(sz[x] < sz[y]) swap(x, y); /// x�� ũ�⸦ �� ũ�� ����� �ش�. smaller to larger�� �̿��� log �ð��� ��ģ��.

            sz[x] += sz[y];
            par[y] = x; /// �� �� ���� ����� union-find�� ���� �۾���(�̻��� �� ���� �ִ� �� ���� ������...)

            /// ���� set�� ���� ��� �Ѵ�.
            for(auto nxt: link[y]){
                link[x].insert(nxt);

                revLink[nxt].erase(revLink[nxt].find(y));
                revLink[nxt].insert(x);
            }
            for(auto nxt: revLink[y]){ /// ������ ������ �����ϱ�.
                link[nxt].erase(link[nxt].find(y));
                link[nxt].insert(x);
            }
            for(auto nxt: coming[y]){
                if(par[nxt] != x) coming[x].insert(nxt);
            }
            link[y].clear(), revLink[y].clear(), coming[y].clear(); /// ���� �������� �޸� �Ƴ���.

            /// set �������� ans �ٽ� ��������.
            ans += sz[x] * ((ll)coming[x].size());
        }
        else if(coming[y].find(px) == coming[y].end()){ /// ������ ���� ó�� �����ִ� ����, ó���� ����.
            link[x].insert(y); /// ���� �߰�.
            revLink[y].insert(x); /// ������ ������ �߰�.

            coming[y].insert(px);

            ans += sz[y];
        }
        printf("%lld\n", ans);
    }
}

Compilation message

joitter2.cpp:9:1: error: expected initializer before 'll'
    9 | ll sz[100002];
      | ^~
joitter2.cpp: In function 'int find(int)':
joitter2.cpp:16:11: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
   16 |     if(x==par[x]) return x;
      |           ^~~
      |           __pstl::execution::v1::par
In file included from /usr/include/c++/9/pstl/glue_algorithm_defs.h:15,
                 from /usr/include/c++/9/algorithm:71,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from joitter2.cpp:1:
/usr/include/c++/9/pstl/execution_defs.h:114:27: note: '__pstl::execution::v1::par' declared here
  114 | constexpr parallel_policy par{};
      |                           ^~~
joitter2.cpp:17:12: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
   17 |     return par[x] = find(par[x]);
      |            ^~~
      |            __pstl::execution::v1::par
In file included from /usr/include/c++/9/pstl/glue_algorithm_defs.h:15,
                 from /usr/include/c++/9/algorithm:71,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from joitter2.cpp:1:
/usr/include/c++/9/pstl/execution_defs.h:114:27: note: '__pstl::execution::v1::par' declared here
  114 | constexpr parallel_policy par{};
      |                           ^~~
joitter2.cpp: In function 'void init()':
joitter2.cpp:22:9: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
   22 |         par[i] = i;
      |         ^~~
      |         __pstl::execution::v1::par
In file included from /usr/include/c++/9/pstl/glue_algorithm_defs.h:15,
                 from /usr/include/c++/9/algorithm:71,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from joitter2.cpp:1:
/usr/include/c++/9/pstl/execution_defs.h:114:27: note: '__pstl::execution::v1::par' declared here
  114 | constexpr parallel_policy par{};
      |                           ^~~
joitter2.cpp:23:9: error: 'sz' was not declared in this scope
   23 |         sz[i] = 1;
      |         ^~
joitter2.cpp: In function 'int main()':
joitter2.cpp:43:20: error: 'sz' was not declared in this scope
   43 |             ans += sz[x] * sz[y]; /// x->y      Ѵ.
      |                    ^~
joitter2.cpp:50:20: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
   50 |                 if(par[nxt] != y) st.insert(nxt);
      |                    ^~~
      |                    __pstl::execution::v1::par
In file included from /usr/include/c++/9/pstl/glue_algorithm_defs.h:15,
                 from /usr/include/c++/9/algorithm:71,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from joitter2.cpp:1:
/usr/include/c++/9/pstl/execution_defs.h:114:27: note: '__pstl::execution::v1::par' declared here
  114 | constexpr parallel_policy par{};
      |                           ^~~
joitter2.cpp:60:13: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
   60 |             par[y] = x; ///     union-find  ۾(̻   ִ   ...)
      |             ^~~
      |             __pstl::execution::v1::par
In file included from /usr/include/c++/9/pstl/glue_algorithm_defs.h:15,
                 from /usr/include/c++/9/algorithm:71,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from joitter2.cpp:1:
/usr/include/c++/9/pstl/execution_defs.h:114:27: note: '__pstl::execution::v1::par' declared here
  114 | constexpr parallel_policy par{};
      |                           ^~~
joitter2.cpp:87:20: error: 'sz' was not declared in this scope
   87 |             ans += sz[y];
      |                    ^~
joitter2.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
joitter2.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~