oj.uz

답안 #3335

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
3335 2013-08-30T12:41:25 Z wookayin 두 섬간의 연결 (kriii1_2) C++
0 / 1
 400 ms 2520 KB 
#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.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 1992 KB Output is correct
2 Correct 80 ms 1992 KB Output is correct
3 Correct 80 ms 1992 KB Output is correct
4 Correct 80 ms 1992 KB Output is correct
5 Correct 36 ms 1992 KB Output is correct
6 Execution timed out 400 ms 2520 KB Program timed out