## 452 - Project Scheduling

Moderator: Board moderators

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### Re: 452, Why WA

@brianfry713...thank you.
-@ce

kev_yu
New poster
Posts: 3
Joined: Sun Dec 29, 2013 8:46 am

### Re: 452, Why WA

I don't understand why I get TLE my algo should run with O(V+E) time complexity. I have test the the test case given here and got it right. First I run topological sort with DFS then DP bottom up

Here is my code

Code: Select all

``````#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <math.h>
#include <bitset>
#include <stack>

#define INF 800000010
using namespace std;

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef pair<int,ii> iii;
typedef vector<iii> viii;
typedef vector<ii> vii;

vi topo;
int dist[110];
bool visited[110];

int xtr[4]={0,0,1,-1};
int ytr[4]={1,-1,0,0};
int maksimum(int a,int b)
{
if (a>b)
{
return a;
}
else
{
return b;
}
}

void toposort(int u)
{
visited[u]=1;
{
if (!visited[S])
{
toposort(S);
}
}
topo.push_back(u);
}

int main()
{
int TC,maks;
int u,v,weight;
char inp,term;
scanf("%d",&TC);
getchar();
getchar();
for (int b=1;b<=TC;b++)
{
if (b!=1) printf("\n");

//Inisialisasi
for (int i=1;i<=60;i++)
{
}
for (int i=1;i<=60;i++)
{
visited[i]=0;
dist[i]=0;
}
maks=0;
inp=getchar();
while ((inp!='\n'))
{
//printf("%c\n",inp);
u=(int)inp-64;
getchar();
scanf("%d",&weight);
term=getchar();
if (term!='\n')
{
inp=getchar();
while ((inp!='\n') && (inp!=EOF))
{
v=(int)inp-64;
inp=getchar();
}
}
if (inp==EOF)
{
break;
}
else
{
inp=getchar();
}
}

//topological sort
for (int i=1;i<=60;i++)
{
if (!visited[i])
{
toposort(i);
}
}

for (int i=topo.size()-1;i>=0;i--)
{
int cur=topo[i];
{
dist[S]=maksimum(dist[S],dist[cur]+we);
}
}
for (int i=31;i<=60;i++)
{
if (maks<dist[i])
{
maks=dist[i];
}
}
printf("%d\n",maks);
}
return 0;
}
``````

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

### Re: 452, Why WA

It looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!

kaushik_acharya
New poster
Posts: 17
Joined: Thu Jul 28, 2005 3:05 pm
Location: Bangalore, India

### Re: 452, Why WA

Got RE.
Here's my code: http://ideone.com/f4nz44

Have done DFS based topological sort like others have mentioned in this thread.
Have also tested the code with the 100 test cases put by Brian Fry.

Wondering where could I have gone wrong.
My experience with Fraudster khari

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

### Re: 452, Why WA

Try changing your tokenize function. It throws a RE if there is a trailing space on a line. I used sscanf().
Check input and AC output for thousands of problems on uDebug!

kaushik_acharya
New poster
Posts: 17
Joined: Thu Jul 28, 2005 3:05 pm
Location: Bangalore, India

### Re: 452, Why WA

brianfry713 wrote:Try changing your tokenize function. It throws a RE if there is a trailing space on a line. I used sscanf().
@brian,
Thanks a lot. I didn't realised that the input lines can have trailing spaces.
I made a change on my tokenize function to check for reaching end of string.
My experience with Fraudster khari

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

### Re: 452, Why WA

Thanks for the test cases Brian Fry. For this problem it requires some work to create testcases.

anando_du
New poster
Posts: 10
Joined: Sun Mar 01, 2015 3:11 pm

### Re: 452 - Project Scheduling

Test cases are too weak i think ... My AC code produces output 0 for
1

A 42
This case

hasan169
New poster
Posts: 1
Joined: Sun Apr 03, 2016 1:23 pm

### Re: 452 - Project Scheduling

i have checked all the inputs of U debug but still getting WA.... can anyone give me special testcase
here is my code https://ideone.com/ZXxfQy