## #1954987

Solution for 2224: Save your cats by btk

Source Code Status Test Cases
Policy: public     Reviewed: 58
00.01 sec    3812 KB    67 lines     1424 bytes    2016-08-08 16:21
```#include<bits/stdc++.h>

using namespace std;
struct I{I(){ios::sync_with_stdio(false);cin.tie(0);cout<<setprecision(10);cout<<fixed;}}init;

namespace dsu{
#define SZ 500000
int mem[2][SZ];
}
class UF{
public:
int *par,*rank;
int find(int x){
if(par[x]==x)return x;
else return par[x]=find(par[x]);
}
bool unite(int x,int y){
x=find(x);y=find(y);
if(x==y)return false;
if(rank[x]<rank[y])par[x]=y;
else{
par[y]=x;
if(rank[x]==rank[y])rank[x]++;
}
return true;
}
bool same(int x,int y){
return find(x)==find(y);
}
UF(int n):par(dsu::mem[0]),rank(dsu::mem[1]){
for(int i=0;i<n;i++)par[i]=i,rank[i]=0;
}
};
int main(){
using P=complex<double>;
int N,M;
cin>>N>>M;
double total=0;
vector<P> xy(N);
for(int i=0;i<N;i++){
double x,y;cin>>x>>y;
xy[i]=P(x,y);
}
using T=tuple<double,int,int>;
vector<T> edge(M);
for(int i=0;i<M;i++){
int p,q;
cin>>p>>q;p--,q--;
double len=abs(xy[p]-xy[q]);
total+=len;
edge[i]=T(len,p,q);
}
sort(edge.begin(),edge.end());
reverse(edge.begin(),edge.end());
UF uf(N);
for(auto &e:edge){
double len;int p,q;
tie(len,p,q)=e;
if(uf.unite(p,q))
total-=len;
}
cout<<total<<endl;

return 0;
}

```
 Compile Error Logs: You are not authorized to see the message.

Status
 Judge: 32/32 C++11 CPU: 00.01 sec Memory: 3812 KB Length: 1424 B 2016-08-08 16:21 2016-08-08 16:21
Results for testcases
 Case # Verdict CPU Time Memory In Out Case Name Case #1: : Accepted 00.00 sec 3160 KB Case #2: : Accepted 00.00 sec 3340 KB Case #3: : Accepted 00.00 sec 3296 KB Case #4: : Accepted 00.00 sec 3320 KB Case #5: : Accepted 00.00 sec 3320 KB Case #6: : Accepted 00.00 sec 3332 KB Case #7: : Accepted 00.00 sec 3368 KB Case #8: : Accepted 00.00 sec 3308 KB Case #9: : Accepted 00.00 sec 3332 KB Case #10: : Accepted 00.00 sec 3284 KB Case #11: : Accepted 00.00 sec 3232 KB Case #12: : Accepted 00.00 sec 3160 KB Case #13: : Accepted 00.00 sec 3284 KB Case #14: : Accepted 00.00 sec 3160 KB Case #15: : Accepted 00.00 sec 3156 KB Case #16: : Accepted 00.00 sec 3340 KB Case #17: : Accepted 00.00 sec 3296 KB Case #18: : Accepted 00.00 sec 3368 KB Case #19: : Accepted 00.00 sec 3372 KB Case #20: : Accepted 00.00 sec 3324 KB Case #21: : Accepted 00.00 sec 3356 KB Case #22: : Accepted 00.00 sec 3160 KB Case #23: : Accepted 00.00 sec 3324 KB Case #24: : Accepted 00.00 sec 3340 KB Case #25: : Accepted 00.00 sec 3236 KB Case #26: : Accepted 00.00 sec 3308 KB Case #27: : Accepted 00.00 sec 3280 KB Case #28: : Accepted 00.01 sec 3412 KB Case #29: : Accepted 00.00 sec 3700 KB Case #30: : Accepted 00.00 sec 3812 KB Case #31: : Accepted 00.00 sec 3628 KB Case #32: : Accepted 00.00 sec 3436 KB
 < prev | / | next >

 Judge Input #  ( | ) Judge Output #  ( | )
Comments

Under Construction.

Categories

Free Tags