452 - Project Scheduling

[@ce]

@brianfry713...thank you.

[kev_yu]

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];
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;
}

[brianfry713]

It looks like you figured it out.

[kaushik_acharya]

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.

[brianfry713]

Try changing your tokenize function. It throws a RE if there is a trailing space on a line. I used sscanf().

[kaushik_acharya]

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.

[vsha041]

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

[anando_du]

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

1

A 42

This case

[hasan169]

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