Submission #19156

#	Time	Username	Problem	Language	Result	Execution time	Memory
19156		kdh9949	두 섬간의 연결 (kriii1_2)	C++98	1 / 1	48 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(ll 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: 1 / 1