Solução OBI 2016

ciclovias.cpp

// Ivan Carvalho
// Ciclovias - Fase 2 Programação Nível 2 - OBI 2016
// O(m*log(n))
#include <bits/stdc++.h>
using namespace std;
typedef struct node* pnode;
const int MAXN = 1e5 + 10;
struct node{
	int val;
	pnode l,r;
	node() : l(NULL),r(NULL),val(0){}
	void update(int left,int right,int x,int delta){
		if(left == right){
			val = max(val,delta);
			return;
		}
		int mid = (left+right)/2;
		val = max(val,delta);
		if(x <= mid){
			if(l == NULL) l = new node;
			l->update(left,mid,x,delta);
		}
		else{
			if(r == NULL) r = new node;
			r->update(mid+1,right,x,delta);
		}
	}
	int query(int left,int right,int i,int j){
		if(left>right||left>j||right<i) return 0;
		if(left >= i && right <= j){
			return val;
		}
		int mid = (left+right)/2;
		int sinistra = (l == NULL) ? 0 : l->query(left,mid,i,j);
		int destra = (r == NULL) ? 0 : r->query(mid+1,right,i,j);
		return max(sinistra,destra);
	}
};
vector<int> grafo[MAXN];
pnode raiz[MAXN];
int maior[MAXN];
int main(){
	int n,m,N;
	scanf("%d %d",&n,&m);
	N = n + 1;
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}
	for(int i=1;i<=n;i++) maior[i] = 1;
	for(int i=1;i<=n;i++) raiz[i] = new node;
	for(int v = n;v >= 1;v--){
		for(int i=0;i<grafo[v].size();i++){
			int u = grafo[v][i];
			raiz[v]->update(1,N,u,maior[u]);
		}
		for(int i=0;i<grafo[v].size();i++){
			int u = grafo[v][i];
			int novo = 2 + raiz[v]->query(1,N,u+1,N);
			maior[u] = max(maior[u],novo);
		}
	}	
	for(int i=1;i<=n;i++) printf("%d ",maior[i]);
	printf("\n");
	return 0;
}