11733 - Airports

[Diaa.Abobaraka]

733 - AIRPORT

Thanks ..got AC .....kindly could you give some other classes that would help me in I/O routines ?

[lbv]

kindly could you give some other classes that would help me in I/O routines ?

Here's all I could find from my old code: http://pastebin.com/rp6rzUK9

Feel free to do with it whatever you want. However, if you want to hear a suggestion, I'd encourage you to use it only as a reference. I think one of the best things you could do is study that code and compare it against other I/O techniques in Java and try to understand what works better and why, and then write your own I/O routines according to your own style.

[just_yousef]

Why TLE

Code: Select all

Solved :D

[lbv]

Why TLE

Your union-find implementation seems slow, turning your program's complexity to O(NM) per test case, which is very high. Try a different implementation; one with path compression, for example.

Also try:

Input

Code: Select all

1
8 5 15
3 1 45
8 2 25
5 8 8
3 4 15
6 2 8

Output

Code: Select all

Case #1: 106 6

[just_yousef]

Why TLE

Your union-find implementation seems slow, turning your program's complexity to O(NM) per test case, which is very high. Try a different implementation; one with path compression, for example.

Thank You, Got AC

[Cloudfrog]

Code in ANSI C
hello. please help me with my code T.T
I'm getting Runtime Error on this problem, but I can't find the reason why. please help

Code: Select all

#include <stdio.h>
#include <string.h>


int size[10000];
int root[10000];


int find(int a){
    if(a==root[a])return a;
    a=root[a];
    return find(a);
}

struct Edge {
  int a;
  int b;
  int w;
};

int comparator(const void *p, const void *q) 
{
    int l = ((struct Edge *)p)->w;
    int r = ((struct Edge *)q)->w; 
    return (l - r);
}
int main()
{
    int T;
    int t;
    int N;
    int M;
    int m;
    int A;
    int x;
    int y;
    int z;
    int q;
    int ans;
    int ports;
    int a;
    int b;
    struct Edge PQ[10000];
    scanf("%d", &T);
    
    for(t = 1; t <= T; t++){
        scanf("%d", &N);   
        scanf("%d", &M);
        scanf("%d", &A);
        int i;
        for(i = 0; i < N; i++){
            size[i] = 1;
            root[i] = i;
        }
        for(m = 0; m < 10000; m++){
            PQ[m].a = 11000;
            PQ[m].b = 11000;
            PQ[m].w = 11000;
        }
        for(m = 0; m < M; m++){
            scanf("%d", &x);
            scanf("%d", &y);
            scanf("%d", &z);
            PQ[m].a = x;
            PQ[m].b = y;
            PQ[m].w = z;
        }
        qsort(PQ, 10000, sizeof(struct Edge), comparator);

        q = 0;
        ans = 0;
        for(m = 0; m < M; m++){
                a=PQ[m].a;
                b=PQ[m].b;
                z=PQ[m].w;
                a=find(a);
                b=find(b);
                if(a!=b && z < A){
                q++;
                ans = ans + PQ[m].w;
                if(size[a]>=size[b]){
                    size[a]  = size[a] + size[b];
                    root[b] = a;
                }
                else{
                        size[b]= + size[b]+ size[a];
                        root[a] = b;
                }
                if(q == N-1) break;
            }
            
        }
        ports = 0;
        ports = N-q;
        ans = ans + ports*A;
        printf("Case #%d: %d %d\n", t, ans, ports);
        
    }    
    return 0;
}

[brianfry713]

0<=M<=100,000

[ehsanulbigboss]

Lots of Thanks to brianfry713

[brianfry713]

Git rid of elements[]