11733 - Airports

All about problems in Volume 117. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Diaa.Abobaraka
New poster
Posts: 3
Joined: Mon Feb 11, 2013 5:44 pm

Re: 11733 - Airports

Post by Diaa.Abobaraka » Sun May 25, 2014 6:32 am

lbv wrote:733 - AIRPORT
Thanks ..got AC .....kindly could you give some other classes that would help me in I/O routines ?

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 11733 - Airports

Post by lbv » Sun May 25, 2014 10:34 pm

Diaa.Abobaraka wrote: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
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 11733 - Airports

Post by just_yousef » Thu Jul 17, 2014 9:09 pm

Why TLE :( :(

Code: Select all

Solved :D
Last edited by just_yousef on Sun Jul 20, 2014 3:24 am, edited 1 time in total.

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 11733 - Airports

Post by lbv » Thu Jul 17, 2014 9:56 pm

just_yousef wrote: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
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 11733 - Airports

Post by just_yousef » Sun Jul 20, 2014 3:25 am

lbv wrote:
just_yousef wrote: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 :D

Cloudfrog
New poster
Posts: 1
Joined: Tue Nov 12, 2013 5:48 pm

Re: 11733 - Airports Runtime Error with C

Post by Cloudfrog » Thu Sep 04, 2014 7:11 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11733 - Airports

Post by brianfry713 » Thu Sep 04, 2014 7:46 pm

0<=M<=100,000
Check input and AC output for thousands of problems on uDebug!

ehsanulbigboss
New poster
Posts: 32
Joined: Tue Jul 22, 2014 1:17 am

Re: 11733 - Airports

Post by ehsanulbigboss » Mon Jan 19, 2015 6:14 pm

Lots of Thanks to brianfry713
Last edited by ehsanulbigboss on Mon Jan 19, 2015 10:30 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11733 - Airports

Post by brianfry713 » Mon Jan 19, 2015 10:18 pm

Git rid of elements[]
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 117 (11700-11799)”