Submission #20213

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20213	2016-04-11T08:39:23 Z	joonas	두 섬간의 연결 (kriii1_2)	C++	1 / 1	44 ms	8 KB

2

#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

#	Verdict	Execution time	Memory	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