Cod sursa(job #534728)

Utilizator loginLogin Iustin Anca login Data 16 februarie 2011 08:59:03
Problema Felinare Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
# include <fstream>
# include <iostream>
# include <vector>
# define DIM 9000
using namespace std;
int n, m, b[4][DIM], v[DIM], sol;
vector<int>G[DIM];

void read ()
{
	ifstream fin ("felinare.in");
	fin>>n>>m;
	int x, y;
	for(int i=1;i<=m;++i)
	{
		fin>>x>>y;
		G[x].push_back(y);
	}
}

int inline max (int k, int x, int y)
{
	int m=0;
	for(int i=x;i<=y;++i)
		if (b[i][k]>m)
			m=b[i][k];
	return m;
}

void f (int k)
{
	v[k]=1;
	for(vector<int>::iterator I=G[k].begin();I!=G[k].end();++I)
	{
		b[0][*I]+=max(k, 0, 3);
		b[1][*I]+=1+max(k, 0, 3);
		b[2][*I]+=max(k, 0, 1)+1;
		b[3][*I]+=max(k, 2, 3)+2;
		if (!v[*I])
			f(*I);
	}
	if (G[k].size()==0)
		sol+=max(k, 0, 3);
}
	
int main ()
{
	read ();
	for(int i=1;i<=n;++i)
		if (!v[i])
		{
			int s=0;
			for(int j=0;j<4;++j)
				s+=b[j][i];
			if (s==0)
				b[1][i]=b[2][i]=1,b[3][i]=2;
			f (i);
		}
	ofstream fout ("felinare.out");
	fout<<sol;
	return 0;
}