Submission #3335

#	Time	Username	Problem	Language	Result	Execution time	Memory
3335		wookayin	두 섬간의 연결 (kriii1_2)	C++98	0 / 1	400 ms	2520 KiB

2

#include <cstdio>
#include <map>

using namespace std;

int n;
int uf[100001];
int sz[100001];

int find(int x) {
        if(uf[x] == x) return x;
        else return uf[x] = find(uf[x]);
}

struct info {
        int m1, m2;
        int p;
};

info merge(int i, int j) {
        i = find(i), j = find(j);
        info ret;

        ret.m1 = sz[i];
        ret.m2 = sz[j];

        // uf[i] = j
        uf[i] = j;
        sz[j] += sz[i];
        sz[i] = 0;

        ret.p = sz[j];
        return ret;
}

int nextInt() {
        int t; scanf("%d", &t); return t;
}

void dealwith(map<int, int> &a) {
        long long ans1 = 0, ans2 = 0;
        for(map<int, int>::iterator it = a.begin(); it != a.end(); ++ it) {
                long long s = it->first, w = it->second;
//              printf("<%d> * %d\n", s, w);

                ans1 += s * (s-1) / 2 * w;
                ans2 += s * (s-1) * (s+1) / 6 * w;
        }
        printf("%lld %lld\n", ans1, ans2);
}

int main() {
        n = nextInt();

        map<int, int> a;
        a[1] = n;

        for(int i = 0; i < n; ++ i)
                uf[i] = i, sz[i] = 1;

        for(int i = 0; i < n - 1; ++ i) {
                int p = nextInt() - 1;
                info in = merge(p, p+1);

                a[in.m1] --;
                a[in.m2] --;
                a[in.p] ++;
                dealwith(a);
        }

        return 0;
}

• Subtask 1: 0 / 1