#1954987

Solution for 2224: Save your cats by btk

Source Code Status Test Cases
    Policy: public     Reviewed: 41    
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