oj.uz

Submission #269591

# Submission time Handle Problem Language Result Execution time Memory
269591 2020-08-17T07:59:41 Z 반딧불(#5114) Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 12 ms 14464 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
int par[100002], 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 += ll(sz[x]) * sz[y]; /// x->y�� ���� ��� �������� ���� ��� �Ѵ�.
            ans += ll(sz[y]) * sz[x]; /// y->x�� ���� ��� �������� ���� ��� �Ѵ�.
            ans -= ll(sz[x]) * ((ll)coming[x].size()) + ll(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 += ll(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]; /// 2ez
        }
        printf("%lld\n", ans);
    }
}

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
joitter2.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Incorrect 12 ms 14464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Incorrect 12 ms 14464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Incorrect 12 ms 14464 KB Output isn't correct
4 Halted 0 ms 0 KB -