oj.uz

답안 #20213

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
20213 2016-04-11T08:39:23 Z joonas 두 섬간의 연결 (kriii1_2) C++
1 / 1
 44 ms 8 KB 
#include <cstdio>
 
typedef long long lld;
 
int r[100001];
lld C[100001];
 
int find(int n){
    if(n == r[n]) return n;
    return r[n] = find(r[n]);
}
 
int merge(int p, int q){
    p = find(p);
    q = find(q);
    if(p != q){
        r[q] = p;
        C[p] += C[q];
        C[q] = 1;
    }
    return C[p];
}
 
lld sum3(int n){
    return n*(n-1LL)*(n+1)/6LL;
}
 
int main(){
    int i, n, k;
    lld S[100001]={0};
    lld pairs = 0, bridges = 0;
    scanf("%d", &n);
    for(i=1; i<=n; ++i){
        r[i] = i, C[i] = 1;
        S[i] = S[i-1] + i;
    }
    for(i=1; i<n; ++i){
        scanf("%d", &k);
        int k0 = find(k), k1 = find(k+1);
        pairs -= S[C[k0]] + S[C[k1]];
        bridges -= sum3(C[k0]) + sum3(C[k1]);
        bridges += sum3(merge(k0, k1));
        pairs += S[C[k0]] * S[C[k1]];
        printf("%lld %lld\n", pairs, bridges);
    }
    return 0;
}

Compilation message

2.cpp: In function 'int main()':
2.cpp:32:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
2.cpp:38:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &k);
                        ^

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 4 KB Output is correct
2 Correct 42 ms 4 KB Output is correct
3 Correct 43 ms 5 KB Output is correct
4 Correct 44 ms 6 KB Output is correct
5 Correct 37 ms 6 KB Output is correct
6 Correct 41 ms 8 KB Output is correct