제출 #19155

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
19155		kdh9949	두 섬간의 연결 (kriii1_2)	C++98	0 / 1	39 ms	1992 KiB

2

#include <cstdio>
#include <algorithm>
typedef long long ll;

struct DisjSet{
    int par[100010];
    int sz[100010];
    DisjSet(int n){
        for(int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
    }
    int Find(int a){
        if(par[a] == a) return a;
        return par[a] = Find(par[a]);
    }
    void Union(int a, int b){
        sz[Find(b)] += sz[Find(a)];
        par[Find(a)] = Find(b);
    }
};

ll ans1, ans2;
int n, c;
ll a, b;
DisjSet *DS;

ll f1(ll x){
    return x * (x - 1) / 2;
}

ll f2(int x){
    return x * (x - 1) * (x + 1) / 6;
}

int main(){
    scanf("%d", &n);
    DS = new DisjSet(n);
    for(int i = 0; i < n - 1; i++){
        scanf("%d", &c);
        a = DS -> sz[DS -> Find(c)];
        b = DS -> sz[DS -> Find(c + 1)];
        ans1 -= f1(a) + f1(b);
        ans2 -= f2(a) + f2(b);
        DS -> Union(c, c + 1);
        ans1 += f1(a + b);
        ans2 += f2(a + b);
        printf("%lld %lld\n", ans1, ans2);
    }
}

• Subtask 1: 0 / 1