10048 - Audiophobia

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

Moderator: Board moderators

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

WAAAAAAAA

Post by I LIKE GN » Fri Sep 02, 2005 12:55 pm

hello all...
i can't find out my bug.....
please help meeeeeee!!!!!!!!!

Code: Select all


got acc removed...
thanks...
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

ACCCCCCC

Post by I LIKE GN » Fri Sep 02, 2005 2:20 pm

never mind
i just got the problem ACC with minor change :P :P :P
thank uuuuuu...
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

event
New poster
Posts: 2
Joined: Sat Oct 29, 2005 12:54 pm

10048 PE

Post by event » Sat Oct 29, 2005 6:49 pm

I generate the output like in example:

Code: Select all

Case #1
80
60
60
 
Case #2
40
no path
80

Does somebody knows why PE?

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Sun Oct 30, 2005 4:59 am

There should be no blank line after the last test case.

n_arun89
New poster
Posts: 2
Joined: Wed Dec 12, 2007 12:28 am
Location: India

10048 Audiophobia w/a why? any critical cases....

Post by n_arun89 » Wed Dec 12, 2007 12:42 am

here is my code can anyone find the problem.....???????

Code: Select all




#include<iostream>
using namespace std;
long long cost[1000][1000];
int q[1000][2];
int n,e,que;

void floyd(int con){             //floyd algo
     int i,j,k;
     for(k=1;k<=n;k++){
     for(j=1;j<=n;j++){
     for(i=1;i<=n;i++){
                      
           cost[i][j]=min(cost[i][j],max(cost[i][k],cost[k][j]));
                        }
                        }
                        }
                       
                        cout<<"Case #"<<con<<endl;
                        for(i=1;i<=que;i++){
                             if(cost[q[i][0]][q[i][1]]>200000000){cout<<"no path"<<endl;}
                             else{            
                        cout<<cost[q[i][0]][q[i][1]]<<endl;}
                        }
                        
                        
                        }        


int main(){
    int x,y,i,j,intensity,con=1;
    while(cin>>n>>e>>que){
                     if(e==0 && n==0 && que==0){break;}
                     else{     
                           for(j=1;j<=n;j++){
                            for(i=1;i<=n;i++){
                                             cost[j][i]=2000000089;
                                             }            //initialising to a max
                                             }
                        
                        for(i=1;i<=e;i++){
                           cin>>x>>y>>intensity;
                           cost[x][y]=intensity;
                           cost[y][x]=intensity;
                           }                      //getting inputs
                          
                        for(i=1;i<=que;i++){
                                cin>>q[i][0]>>q[i][1];
                                }                           //getting query co-ordinates


                                floyd(con++);           //con is the test case number
                                cout<<endl;
                                }
                                } 
                                return 0;
                                }                      
:-?
Programming is Fun

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Tue Mar 11, 2008 7:28 pm

thanks i got acc
here just little tricks
that u have to check the new line.
''I want to be most laziest person in the world''

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Tue Mar 11, 2008 7:30 pm

don't create new thread . Check the board first.
''I want to be most laziest person in the world''

SyFy
New poster
Posts: 13
Joined: Tue Jun 19, 2012 12:16 pm
Location: Russia, Vladimir
Contact:

Re: 10048 - Audiophobia

Post by SyFy » Wed Jun 27, 2012 2:47 pm

Solved this problem with DSU + Kruskal + Floyed... is it ok?
Accepted JAVA 0.640

pls tell me how to solve this problem using only Floyed algo. :D

Thx.

abbir.ku
New poster
Posts: 3
Joined: Sat Nov 09, 2013 10:04 am

Re: 10048 - Audiophobia

Post by abbir.ku » Wed Apr 09, 2014 1:46 pm

I have tried all the test cases but still wrong answer . plz help . Here is my code . I have used prims algorithm .

Code: Select all



#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define pb(x) push_back(x)
#define MAX 210
#define initialize(a,b,c) for(int i=0;i<c;i++)a[i] = b
#define mem(x,y) memset(x,y,sizeof(x))
#define MAXINT 999999999
#define READ(in) freopen(in,"r",stdin)
#define WRITE(out) freopen(out,"w",stdout)

using namespace std;

struct edge{
    int vertex;
    int weight;

    bool operator < (const edge& p) const{
        return weight>p.weight;
    }
};

vector<edge> adjList[MAX];//
vector<int> trail;//
bool intree[MAX];
int parent[MAX];
int child[MAX];
int dist[MAX];
int last;

void addToList(int st,int en,int weight){
    edge e1;
    e1.vertex = en;
    e1.weight = weight;
    adjList[st].pb(e1);

    e1.vertex = st;
    e1.weight = weight;
    adjList[en].pb(e1);
}

void mst_prims(int start){
    initialize(dist,MAXINT,MAX);
    mem(parent,-1);
    mem(child,-1);
    mem(intree,false);


    edge e1,u;
    int v,w,Size;
    priority_queue<edge> pq;

    dist[start] = 0;
    intree[start] = true;
    e1.vertex = start;
    e1.weight = 0;
    pq.push(e1);

    while(!pq.empty()){
        u = pq.top();
        pq.pop();
        Size = adjList[u.vertex].size();

        intree[u.vertex] = true;

        last =u.vertex;

        rep(i,Size){
            v = adjList[u.vertex][i].vertex;
            w = adjList[u.vertex][i].weight;

            if((intree[v]==false)&&(dist[v]>w)){
                e1.vertex = v;
                e1.weight = w;
                pq.push(e1);

                parent[v] = u.vertex;
                child[u.vertex] = v;
                dist[v] = w;
            }
        }
    }
}

int parentMaximum(int last,int en){
    vector<int> weights;
    int x = last;
    while(x!=-1){
        weights.pb(dist[x]);
        x = parent[x];
    }
    sort(weights.begin(),weights.end());
    return weights[weights.size()-1];
}

int childMaximum(int en){
    vector<int> weights;
    int x = en;
    while(x!=-1){
        weights.pb(dist[x]);
        x = parent[x];

    }
    sort(weights.begin(),weights.end());
    return weights[weights.size()-1];
}


int main()
{
    //READ("in2.txt");
    //WRITE("out.txt");
    int n,e,q;
    int a,b,w;
    int st,en;
    int tCase = 0;
    int x1,x2;
    bool isThere = false;

    while(cin>>n>>e>>q){

        if( (n==0) && (e==0) && (q==0) ){
            break;
        }

        rep(i,e){
            scanf("%d %d %d",&a,&b,&w);
            addToList(a,b,w);
        }

        if(isThere){
            printf("\n");
        }
        isThere = true;

        printf("Case #%d\n",(tCase+1));
        tCase = tCase + 1;

        rep(j,q){
            scanf("%d %d",&st,&en);
            mst_prims(st);

            if( (st<=0)||(st>n)|| (en<=0)||(en>n) ){
                printf("0\n");
                continue;
            }

            if(intree[en]){
                x1 = parentMaximum(last,en);
                x2 = childMaximum(en);
                (x1<x2)?printf("%d\n",x1):printf("%d\n",x2);
            }else{
                printf("no path\n");
            }
        }

        rep(m,n+1){
            adjList[m].clear();
        }
    }

    return 0;
}

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

Re: 10048 - Audiophobia

Post by lbv » Wed Apr 09, 2014 5:20 pm

abbir.ku wrote:I have tried all the test cases but still wrong answer . plz help . Here is my code . I have used prims algorithm .
Have you really tried all test cases given here in the forums? The post just above yours, for example, contains multiple instances of cases where your code prints different answers.

Here's a few additional small cases for you to check:

Input

Code: Select all

4 6 1
1 4 32
1 2 88
2 4 70
3 2 75
3 1 81
3 4 79
2 3

5 7 1
5 3 73
4 5 91
2 5 54
1 2 26
2 4 25
4 3 6
1 4 64
1 5

5 6 1
3 2 76
4 3 23
5 1 44
2 5 70
4 1 54
3 5 85
4 2

0 0 0
Output

Code: Select all

Case #1
75

Case #2
54

Case #3
70
In addition to this, consider that running Prim's algorithm for each query has a prohibitive complexity, given the constraints described in the problem statement. There is another algorithm which can help you answer all queries much more quickly. Take your time to read the previous posts for more tips.

P.S. When posting code in the forums, please use the code tags (see the buttons above the text box while you're writing your messahge). Thanks.

stronk111
New poster
Posts: 4
Joined: Tue Nov 11, 2014 3:20 am

Re: 10048 - Audiophobia

Post by stronk111 » Tue Nov 11, 2014 3:24 am

I can't find bug in my code. My solution is based on MST and DFS.I have tried many random test cases but still I get WA. Can you help me?

Code: Select all

removed got AC
Last edited by stronk111 on Tue Nov 11, 2014 1:11 pm, edited 2 times in total.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10048 - Audiophobia

Post by lighted » Tue Nov 11, 2014 7:41 am

Always print newline after each line, also after last line. Print blank line between test cases. I sent you PM.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

stronk111
New poster
Posts: 4
Joined: Tue Nov 11, 2014 3:20 am

Re: 10048 - Audiophobia

Post by stronk111 » Tue Nov 11, 2014 1:13 pm

Thank you. I was a little confused how output should look like.

Post Reply

Return to “Volume 100 (10000-10099)”