10449 - Traffic

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

Moderator: Board moderators

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10449 - Traffic

Post by Mukit Chowdhury » Thu Aug 07, 2014 5:44 am

Got TLE... Help please... :(

Code: Select all

Accepted... :) 
Last edited by Mukit Chowdhury on Thu Aug 07, 2014 12:27 pm, edited 1 time in total.

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

Re: 10449 - Traffic

Post by lbv » Thu Aug 07, 2014 10:45 am

Mukit Chowdhury wrote:Got TLE... Help please... :(
The method you use to read input:

Code: Select all

      while(~scanf("%d",&n))
is interesting, but it gets the program stuck in an infinite loop if the input happens to contain strange characters at the end of the file, which apparently is the case for this problem. You could try instead:

Code: Select all

      while(scanf("%d",&n) == 1)
Also try the following case:

Input

Code: Select all

15 5 19 16 15 5 1 2 8 6 11 2 1 6 11 18
16
13 1
13 14
1 11
6 12
8 1
9 3
15 2
13 6
13 15
7 14
15 14
8 13
6 14
15 1
9 14
14 12
15
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Output

Code: Select all

Set #1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10449 - Traffic

Post by Mukit Chowdhury » Thu Aug 07, 2014 12:33 pm

lbv wrote: The method you use to read input:

Code: Select all

      while(~scanf("%d",&n))
is interesting, but it gets the program stuck in an infinite loop if the input happens to contain strange characters at the end of the file, which apparently is the case for this problem. You could try instead:

Code: Select all

      while(scanf("%d",&n) == 1)
I tried with

Code: Select all

    while(scanf("%d",&n) != EOF)
but it also failed... :( and gave me same verdict... :/
what kind of strange character can appear in end of file ??? would you please give me a example ??? it will really help.... :)
And your test case is really good... I should have thought about that facts.... :/ >:(

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

Re: 10449 - Traffic

Post by lbv » Thu Aug 07, 2014 9:24 pm

Mukit Chowdhury wrote: I tried with (..)
but it also failed... :( and gave me same verdict... :/
what kind of strange character can appear in end of file ??? would you please give me a example ??? it will really help.... :)
Anything that doesn't conform to what scanf understands as an integer would cause the problem.

EOF will be returned by scanf if the end of file is reached before doing the first conversion (successful or not). If however, the end of file is not reached, but the first conversion fails, then scanf will return zero.

For example, if the input for this problem is:

Code: Select all

5 6 7 8 9 10
6
1 2
2 3
3 4
1 5
5 4
4 5
2
4
5
Then in the second iteration of the loop, scanf would return EOF, because there's nothing left to read.

If, on the other hand, the input is something like:

Code: Select all

5 6 7 8 9 10
6
1 2
2 3
3 4
1 5
5 4
4 5
2
4
5
A
Then it returns zero on the second iteration; the "A" can't be read into an int, scanf stops at that point and returns the number of matches so far, which is zero.

It is a little tricky, but it is not difficult to avoid this type of problems. The cleanest and most robust way to read data with scanf is, I think, to always compare its return value with the number of variables you're expecting to read.

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10449 - Traffic

Post by Mukit Chowdhury » Fri Aug 15, 2014 11:42 am

Humm... Thanks... :)
But the question is, as the problem statement says,

Code: Select all

The first line of each test case contains n (the number of junctions, 0 <= n <= 200) 
then why there will be input like 'A' ??? :/
It's first time, I've got TLE for this kind of reason.... :/

'A' can't be number of junction, right ???
Anyway, thanks again... :)
Last edited by Mukit Chowdhury on Sun Aug 31, 2014 5:47 am, edited 1 time in total.

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

Re: 10449 - Traffic

Post by brianfry713 » Sat Aug 16, 2014 12:50 am

You deleted your full code so I can't try to explain why it wasn't working before.
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10449 - Traffic

Post by Mukit Chowdhury » Sun Aug 31, 2014 5:46 am

The code given below is my AC code. Here I've taken input using

Code: Select all

while(scanf("%d",&n)==1)

but when I used

Code: Select all

while(~scanf("%d",&n))
or

Code: Select all

while(scanf("%d",&n)!=EOF)
I got the verdict TLE !!! It astonished me, as it had never happened before with me.... Without this change, my full code is same... :O

Code: Select all

Deleted...

Sorry for late reply... I've not checked mail... :(
Last edited by Mukit Chowdhury on Thu Sep 04, 2014 6:10 am, edited 1 time in total.

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

Re: 10449 - Traffic

Post by brianfry713 » Wed Sep 03, 2014 8:15 pm

Yes it appears that the judge's input does not conform to the problem statement. There is a non-digit char after the last input. It is always safer to use the "while(scanf("%d", &n) == 1) {" style.
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10449 - Traffic

Post by Mukit Chowdhury » Thu Sep 04, 2014 6:15 am

brianfry713 wrote:Yes it appears that the judge's input does not conform to the problem statement. There is a non-digit char after the last input.
Though it sounds strange according to problem statement... anyway... Thanks for ensuring me about non digit character of the last input... :)

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

Re: 10449 - Traffic

Post by LazyTym » Sun Oct 19, 2014 6:56 am

Help!!
i can not understand the problem statement.........Can anyone help me to understand this problem ?????????

thanks in advance

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

Re: 10449 - Traffic

Post by brianfry713 » Tue Oct 21, 2014 8:20 pm

You can solve it using the Floyd-Warshall algorithm.
Check input and AC output for thousands of problems on uDebug!

nada_elnokaly
New poster
Posts: 3
Joined: Thu Oct 23, 2014 12:29 am

Re: 10449 - Traffic

Post by nada_elnokaly » Thu Oct 23, 2014 12:38 am

I am getting WA
I used Bellman Ford to get the minimum distance +check if there's -ve cycles + handling the nodes that are not connected with the node 0 , also using while(scanf()==1){}

I think I handled most of the bugs discussed here and passes all the testcases that are posted here

I need help please :D

my code:

Code: Select all

#include <bits/stdc++.h>
using namespace std;
const int INF=100000000;
int cost[505],weight[505][505],dist[505],inCycle[505];
vector<int>adj[505];
int main(){
	int n,r,a,b,t=0;
	while(scanf("%d",&n)==1){
		t++;
		for(int i=0;i<n;i++){
			scanf("%d",&cost[i]);
			adj[i].clear();
		}
	
		scanf("%d",&r);

		for(int i=0;i<r;i++){
			scanf("%d%d",&a,&b);
			a--; b--;
			adj[a].push_back(b);
			weight[a][b]=(cost[b]-cost[a])*(cost[b]-cost[a])*(cost[b]-cost[a]);
		}
		
		for(int i=0;i<n;i++)dist[i]=INF;
		dist[0]=0;
		for(int k=0;k<n;k++)
			for(int i=0;i<n;i++)
				for(int j=0;j<(int)adj[i].size();j++){
					int u=i,v=adj[i][j];
					if(dist[u]==dist[v] && dist[u]==INF)continue;
					
					dist[v]=min(dist[v],dist[u]+weight[u][v]);
				
				}
		
		
		memset(inCycle,0,sizeof inCycle);
		for(int i=0;i<n;i++)
			for(int j=0;j<(int)adj[i].size();j++){
				int u=i,v=adj[i][j];
				if(dist[u]+weight[u][v]<dist[v]){
					inCycle[v]=1;
				}
			}
		int q;
		printf("Set #%d\n",t);
	
		scanf("%d",&q);
		for(int i=0;i<q;i++){
			scanf("%d",&a);
			a--; 
			if(dist[a]<3 || inCycle[a] || dist[a]==INF)printf("?\n");
			else printf("%d\n",dist[a]);
		}			
		
	}
	return 0;
}
Last edited by brianfry713 on Thu Oct 23, 2014 9:06 pm, edited 1 time in total.
Reason: Added code blocks

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

Re: 10449 - Traffic

Post by brianfry713 » Fri Oct 24, 2014 12:40 am

There is probably an issue with the way you find negative cycles. Read this thread for ideas, or use the Floyd-Warshall algorithm.
Check input and AC output for thousands of problems on uDebug!

amp15
New poster
Posts: 1
Joined: Thu Mar 31, 2016 12:02 pm

Re: 10449 - Traffic

Post by amp15 » Sat May 14, 2016 11:29 am

My code passed all the test cases of UDebug....Still getting WA !! Please help anyone :(

Code: Select all

#include <bits/stdc++.h>

#define ms(a,b)         memset(a,b,sizeof(a))
#define pb(a)           push_back(a)
#define db              double
#define ft              float
#define ll              long long
#define ull             unsigned long long
#define ff              first
#define ss              second
#define sz(x)           x.size()
#define qu              queue
#define pqu             priority_queue
#define vc              vector
#define vi              vector<int>
#define vll             vector<long long>
#define pii             pair<int,int>
#define pis             pair<int,string>
#define psi             pair<string,int>
#define all(x)          x.begin(),x.end()
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n)      for(int i=0;i<n;i++)
#define loop1(i,n)      for(int i=1;i<=n;i++)
#define stlloop(x)     for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)       __gcd(a, b)
#define lcm(a, b)       ((a)*((b)/gcd(a,b)))
#define case(z,x)       cout<<"Case "<<i<<": "<<x<<endl
#define case(z)         cout<<"Case "<<z<<": "
#define PI              3.14159265358979323846264338328
#define valid(tx,ty)    tx>=0 && tx<r && ty>=0 && ty<c
#define MAX             300
#define inf             10000000

/*---------------------------Graph Moves-----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------------------------*/

using namespace std;

int dis[MAX],parent[MAX];
vector<int>gu,gv,cost;
int node,edge;
map <int, int> mp;

bool bellman_ford()
{
    loop0(i,MAX)
    {
        dis[i]=inf;
    }
    dis[1]=0;
    loop1(i,node)
    {
        bool change=0;
        loop0(j,edge)
        {
            int u=gu[j];
            int v=gv[j];
            if(dis[u]+cost[j]<dis[v])
            {
                change=1;
                dis[v]=dis[u]+cost[j];
            }
        }
        if(change==0) return 1;
    }
}

int main()
{
    CIN;
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    int n_cost,t;
    t=0;
    while(cin>>node)
    {
        //cout<<endl;
        t++;
        loop1(i,node)
        {
            cin>>n_cost;
            mp[i]=n_cost;
        }
        cin>>edge;
        loop0(i,edge)
        {
            int from,to,w;
            cin>>from>>to;
            gu.pb(from);
            gv.pb(to);
            w=mp[to]-mp[from];
            cost.pb(w*w*w);
        }
        int q,n;
        cin>>q;
        cout<<"Set #"<<t<<endl;
        int a=bellman_ford();
        loop0(i,q)
        {
            cin>>n;
            if(dis[n]<3 || dis[n]>100000)
            {
                cout<<"?"<<endl;
            }
            else
            {
                cout<<dis[n]<<endl;
            }
        }
        gu.clear();
        gv.clear();
        cost.clear();
        mp.clear();
    }
    return 0;
}

Post Reply

Return to “Volume 104 (10400-10499)”