oj.uz

Submission #269491

# Submission time Handle Problem Language Result Execution time Memory
269491 2020-08-17T07:22:28 Z 반딧불(#5114) Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 8 ms 9728 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]; /// ������ �͵��� �����̴�.
int sum[100002]; /// indegree.
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);
        x = find(x), y = find(y); /// x -> y�� ���� ������ ��ġ�̴�.

        if(x==y || link[x].find(y) != link[x].end()){
            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]) * sum[x] + ll(sz[y]) * sum[y]; /// �ϴ� indegree count�� ��� ���� ����. ���߿� �ٽ� ��ĥ ���̴�.
            sum[x] -= link[y].count(x); /// �ҿ����� y->x ������ ������ �����ؾ� �Ѵ�.

            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];
            sum[x] += sum[y];
            par[y] = x; /// �� �� ���� ����� union-find�� ���� �۾���(�̻��� �� ���� �ִ� �� ���� ������...)

            /// ���� set�� ���� ��� �Ѵ�.
            for(auto nxt: link[y]){
                link[x].insert(nxt);
                sum[nxt] += sz[x]; /// �̶� sum �����ϴ� �� ���� ����.

                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);
            }
            link[y].clear(), revLink[y].clear(); /// ���� �������� �޸� �Ƴ���.

            /// set �������� ans �ٽ� ��������.
            ans += ll(sz[x]) * sum[x];
        }
        else{ /// ������ ���� ó�� �����ִ� ����, ó���� ����.
            link[x].insert(y); /// ���� �߰�.
            revLink[y].insert(x); /// ������ ������ �߰�.
            sum[y]++; /// �����ϰ� �ȴ�.

            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 Incorrect 8 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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