#include<stdio.h>
#include<set>
using namespace std;
long long arr[100001], arr2[100001];
int n, parent[100001], size[100001];
set<int> s;
set<int>::iterator iter;
int find(int idx){
if(parent[idx]==idx)
return idx;
return parent[idx]=find(parent[idx]);
}
void Union(int a, int b){
int tmp;
a=find(a);
b=find(b);
if(size[a]<size[b]){
tmp=a;
a=b;
b=tmp;
}
parent[b]=a;
if(size[b]==1){
if(size[a]==1)
s.insert(a);
}
else{
iter=s.find(b);
s.erase(iter);
}
size[a]+=size[b];
}
int main(){
int i, num;
long long r1, r2;
scanf("%d", &n);
for(i=1;i<n+1;++i){
arr[i]=(long long)i*((long long)i-1)/2;
arr2[i]=arr2[i-1]+arr[i];
parent[i]=i;
size[i]=1;
}
for(i=1;i<n;++i){
scanf("%d", &num);
Union(num, num+1);
for(r1=r2=0, iter=s.begin();iter!=s.end();++iter){
r1+=arr[size[*iter]];
r2+=arr2[size[*iter]];
}
printf("%lld %lld\n", r1, r2);
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
400 ms |
3948 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
