Submission #3343

#	Time	Username	Problem	Language	Result	Execution time	Memory
3343		wookayin	두 섬간의 연결 (kriii1_2)	C++98	0 / 1	40 ms	1992 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;
}

struct P {
        long long first;
        long long second;
        P(long long first, long long second) : first(first), second(second) {}
};

long long go(long long k, int w) {
        return k*(k-1)/2*w;
}
long long go2(long long k, int w) {
        return k*(k-1)*(k+1)/6*w;
}

int main() {
        n = nextInt();

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

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

        long long ans1 = go(1LL, n);
        long long ans2 = go2(1LL, n);

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

                ans1 = ans1 - go(in.m1, a[in.m1]);
                ans1 = ans1 - go(in.m2, a[in.m2]);
                ans2 = ans2 - go2(in.m1, a[in.m1]);
                ans2 = ans2 - go2(in.m2, a[in.m2]);

                a[in.m1] --;
                a[in.m2] --;
                a[in.p] ++;
                ans1 = ans1 + go(in.p, a[in.p]);
                ans2 = ans2 + go2(in.p, a[in.p]);

                printf("%lld %lld\n", ans1, ans2);
        }

        return 0;
}

• Subtask 1: 0 / 1