452 - Project Scheduling
Moderator: Board moderators
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
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];
vii AdjList[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;
for (int i=0;i<AdjList[u].size();i++)
{
int S=AdjList[u][i].first;
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++)
{
AdjList[i].clear();
}
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();
AdjList[u].push_back(ii(u+30,weight));
if (term!='\n')
{
inp=getchar();
while ((inp!='\n') && (inp!=EOF))
{
v=(int)inp-64;
AdjList[u+30].push_back(ii(v,0));
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];
for(int j=0;j<AdjList[cur].size();j++)
{
int S=AdjList[cur][j].first;
int we=AdjList[cur][j].second;
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;
}
-
- 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!
-
- 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.
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
-
- 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!
-
- New poster
- Posts: 17
- Joined: Thu Jul 28, 2005 3:05 pm
- Location: Bangalore, India
Re: 452, Why WA
@brian,brianfry713 wrote:Try changing your tokenize function. It throws a RE if there is a trailing space on a line. I used sscanf().
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
Re: 452, Why WA
Thanks for the test cases Brian Fry. For this problem it requires some work to create testcases.
Re: 452 - Project Scheduling
Test cases are too weak i think ... My AC code produces output 0 for
This case1
A 42
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
here is my code https://ideone.com/ZXxfQy