oj.uz

Submission #19156

# Submission time Handle Problem Language Result Execution time Memory
19156 2016-02-19T05:37:06 Z kdh9949 두 섬간의 연결 (kriii1_2) C++
1 / 1
 48 ms 1992 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1992 KB Output is correct
2 Correct 0 ms 1992 KB Output is correct
3 Correct 41 ms 1992 KB Output is correct
4 Correct 36 ms 1992 KB Output is correct
5 Correct 48 ms 1992 KB Output is correct
6 Correct 39 ms 1992 KB Output is correct