# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
16465 | gs14004 | 두 섬간의 연결 (kriii1_2) | C++14 | 60 ms | 1868 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
typedef long long lint;
struct disj{
int pa[100005], sz[100005];
void init(int n){
for(int i=0; i<=n; i++){
pa[i] = i;
sz[i] = 1;
}
}
int find(int x){
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
int getsize(int x){
return sz[find(x)];
}
bool uni(int p, int q){
p = find(p);
q = find(q);
pa[q] = p;
sz[p] += sz[q];
}
}disj;
lint f(int x){
return 1ll * x * (x-1) / 2;
}
int main(){
int n;
scanf("%d",&n);
disj.init(n);
lint p1 = 0, p2 = 0;
for(int i=0; i<n-1; i++){
int x;
scanf("%d",&x);
p1 -= f(disj.getsize(x));
p1 -= f(disj.getsize(x+1));
p1 += f(disj.getsize(x) + disj.getsize(x+1));
p2 += f(disj.getsize(x)) * disj.getsize(x+1);
p2 += f(disj.getsize(x+1)) * disj.getsize(x);
p2 += 1ll * disj.getsize(x) * disj.getsize(x+1);
disj.uni(x, x+1);
printf("%lld %lld\n",p1, p2);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |