Seletiva IOI 2015

estacao.cpp

// Ivan Carvalho
// Estação - Seletiva IOI - OBI 2015
#include <bits/stdc++.h>
#define MAXN 200010
using namespace std;
vector<int> grafo[MAXN],pares1,pares2,impares1,impares2;
queue<int> fila1, fila2;
int grau1[MAXN],grau2[MAXN],nivel1[MAXN],nivel2[MAXN],maximo1=2 , maximo2=2, n,m;
int main(){
	scanf("%d %d",&n,&m);
	pares1.push_back(1);
	pares2.push_back(2);
	impares1.push_back(2);
	impares2.push_back(1);
	for(int i=0;i<m;i++){
		int u,op,v;
		scanf("%d %d %d",&u,&op,&v);
		if (op == -1) swap(u,v);
		grau1[v]++;
		grau2[v]++;
		grafo[u].push_back(v);
		if (u % 2 == 0){
			nivel1[u] = 1;
			nivel2[u] = 2;
		}
		else {
			nivel1[u] = 2;
			nivel2[u] = 1;
		}
	}
	for(int i=1;i<=2*n;i++){
		if (!grau1[i] && !grafo[i].empty()){
			fila1.push(i);
			fila2.push(i);
		}
	}
	while(!fila1.empty()){
		int davez = fila1.front();
		fila1.pop();
		for(int i=0;i<grafo[davez].size();i++){
			int atual = grafo[davez][i];
			grau1[atual]--;
			if (grau1[atual] == 0){
				fila1.push(atual);
				if (atual % 2 == 0){
					vector<int>::iterator it = upper_bound(pares1.begin(),pares1.end(),nivel1[davez]);
					if (it == pares1.end()){
						maximo1++;
						nivel1[atual] = maximo1;
						pares1.push_back(nivel1[atual]);
					}
					else nivel1[atual] = *it;
				}
				else {
					vector<int>::iterator it = upper_bound(impares1.begin(),impares1.end(),nivel1[davez]);
					if (it == impares1.end()){
						maximo1++;
						nivel1[atual] = maximo1;
						impares1.push_back(nivel1[atual]);
					}
					else nivel1[atual] = *it;
				}
			}
		}
	}
	while(!fila2.empty()){
		int davez = fila2.front();
		fila2.pop();
		for(int i=0;i<grafo[davez].size();i++){
			int atual = grafo[davez][i];
			grau2[atual]--;
			if (grau2[atual] == 0){
				fila2.push(atual);
				if (atual % 2 == 0){
					vector<int>::iterator it = upper_bound(pares2.begin(),pares2.end(),nivel2[davez]);
					if (it == pares2.end()){
						maximo2++;
						nivel2[atual] = maximo2;
						pares2.push_back(nivel2[atual]);
					}
					else nivel2[atual] = *it;
				}
				else {
					vector<int>::iterator it = upper_bound(impares2.begin(),impares2.end(),nivel2[davez]);
					if (it == impares2.end()){
						maximo2++;
						nivel2[atual] = maximo2;
						impares2.push_back(nivel2[atual]);
					}
					else nivel2[atual] = *it;
				}
			}
		}
	}
	//printf("P1 : %lu P2 : %lu I1 : %lu I2 : %lu\n",pares1.size(),pares2.size(),impares1.size(),impares2.size());
	printf("%d\n",min(maximo1,maximo2));
	return 0;
}