Submission 1089 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
1089	20/05/2013 15:17:03	otero1991	G - Campañas publicitarias	Accepted	1607	5.3 KiB	GNU G++ 5.1.0

Code

#include <cstdio>
#include <sstream>
#include <iostream>
#include <cassert>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <complex>
#include <cstring>
#include <stack>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define FOR(i,n) for (int i = 1; i <= (n); ++i)
#define REP(i,n) for (int i = 0; i < (n); ++i)
#define REPI(i,c) for (typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define ALL(c) c.begin(), c.end()
#define SZ(x) ((int)(x).size())
#define MP make_pair

#define DB(x) cout << #x << " = " << x << endl;
#define CK(x) if(!(x)) cout << '(' << #x << ") is false!!!" << endl;

typedef long long int64;
typedef unsigned long long uint64;
typedef complex<int> point;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int INF = 1 << 30;
const double EPS = 1e-7;

const int MAXV = 100010;

int V,E;
vector<int> G[MAXV];
vector<int> GR[MAXV];

int indeg[MAXV];
vector<int> topsort;
int dst[MAXV];

/******Strongly Connected components******/
int C;
int dtime;
int num[MAXV], low[MAXV], cmp[MAXV];
bool bio[MAXV];
stack<int> S;

void dfs(int u)
{
	num[u] = low[u] = ++dtime;
	S.push(u);

int s = G[u].size();
	for (int i = 0; i < s; i++)
	{
		int v = G[u][i];

if (!num[v])
		{
			dfs(v);
			low[u] = min(low[u], low[v]);
		}
		else if (!bio[v])low[u] = min(low[u], num[v]);
	}
	if (low[u] == num[u])
	{
		while (!bio[u])
		{
			cmp[S.top()] = C;
			bio[S.top()] = true;
			S.pop();
		}
		C++;
	}
}
/*************************************/

int main()
{
	//ios::sync_with_stdio(false);
	cin>>V>>E;

//Read the graph
	for(int i = 0; i < E; i++)
	{
		int a,b; cin>>a>>b;
		G[a].push_back(b);
	}
	//Find strongly connected components
	for(int i = 0; i < V; i++)
	{
		if(!num[i])dfs(i);
	}

//Reduced graph
	for(int i = 0; i < V; i++)
	{
		for(int j = 0; j < (int)G[i].size(); j++)
		{
			int v = G[i][j];
			if(cmp[i] != cmp[v])
			{
				GR[cmp[i]].push_back(cmp[v]);
				indeg[cmp[v]]++;
			}
		}
	}
	//Top sort
	queue<int> Q;
	for(int i = 0; i < C; i++)
		if(indeg[i]==0)Q.push(i);
	while(!Q.empty())
	{
		int v = Q.front();
		topsort.push_back(v);
		Q.pop();
		for(int j = 0; j < (int)GR[v].size(); j++)
		{
			indeg[GR[v][j]]--;
			if(indeg[ GR[v][j] ] == 0)
				Q.push( GR[v][j] );
		}
	}
	assert((int)topsort.size() == C);
	//Maximun walk
	int ans = 0;
	for(int i = 0; i < C; i++)
	{
		int u = topsort[i];
		for(int j = 0; j < (int)GR[u].size(); j++)
		{
			int v = GR[u][j];
			if(dst[u]+1 > dst[v])
			{
				dst[v] = dst[u]+1;
				ans = max(ans,dst[v]);
			}
		}
	}
	cout<<ans+1<<endl;
    return 0;
}
//Daniel Otero Baguer (UH++)

Judgement Details

Test 01: 0.015 0.000 3800K ok
Test 02: 0.018 0.000 3796K ok
Test 03: 1.867 1.607 5404K ok
Test 04: 0.019 0.000 3796K ok
Test 05: 0.014 0.000 3796K ok
Test 06: 0.013 0.000 3800K ok
Test 07: 0.013 0.000 3796K ok
Test 08: 0.024 0.016 3872K ok
Test 09: 0.034 0.031 3956K ok
Test 10: 0.065 0.047 4220K ok
Test 11: 0.123 0.094 4588K ok
Accepted

Matcom Online Grader