Desafios de Programação no Verão de 2011 - Prova 05 - Equipe

Vídeo: Discussão sobre os problemas

Algumas soluções dos competidores

Team building (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <string.h>
#include <set>

using namespace std;

const int NMAX = 100000;

int prox[NMAX], M[NMAX], lbl[NMAX];
int go[NMAX];
int achei;

void dfs(int u, int m) {
	while (1) {
		M[u] = m;
		int v = prox[u];

		if (M[v] == m) {
			for (int p = v; p != u; p = prox[p]) {
				lbl[p] = u;
			}
			achei = v;
		}

		if (!M[v]) {
			u = v;
		} else {
			break;
		}
	}
}

int main() {
	int n;
	scanf("%d", &n);
	set <int> minimo;
	for (int i = 0; i < n; i++) {
		scanf("%d", &prox[i]);
		prox[i]--;
		lbl[i] = i;
	}
	memset(go, 0, sizeof(go));
	for (int i = 0; i < n; i++) {
		go[prox[i]] = 1;
	}
	memset(M, 0, sizeof(M));
	int mincount = 0;
	for (int i = 0; i < n; i++) {
		if (!go[i]) {
			mincount++;
			dfs(i, i+1);
		}
	}
	for (int i = 0; i < n; i++) {
		if (!M[i]) {
			achei = -1;
			dfs(i, i+1);
			if (achei == i) {
				mincount++;
			}
		}
	}
	set<int> maximo;
	for (int i = 0; i < n; i++) {
		maximo.insert(lbl[i]);
	}
	printf("%d %d\n", mincount, maximo.size());
	return 0;
}

Yet Another Answer (por [IME-USP] Isso é tudo pessoal)

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

#define N 1024
#define MAX 10100

int pd[N][MAX];

#define pii pair<int,int> 

struct X {
	int saldo;
	int mini;
	int tam;
	int id;
};

X make_parenteses(int saldo, int mini, int tam,int id) {
	X novo;
	novo.saldo = saldo;
	novo.mini = mini;
	novo.tam = tam;
	novo.id = id;
	return novo;
}

X v[N];
int n;

int vamo(int pos, int acu) {
	if(pos == n) {
		if(acu == 0) return pd[pos][acu] = 0;
		return -2;
	}
	if(pd[pos][acu] != -1) return pd[pos][acu];

	int resp = -2;

	if(acu == 0) resp = 0;

	if(acu + v[pos].saldo >= 0 && acu + v[pos].mini >= 0) {
		int r = vamo(pos+1, acu + v[pos].saldo);
		if(r >= 0) {
			resp = max(resp, r + v[pos].tam);
		}
	}
	resp = max(resp, vamo(pos+1, acu));
	return pd[pos][acu] = resp;
}

int grupo(X a) {
	if(a.saldo >= 0 && a.mini >= 0) return 0;
	if(a.saldo >= 0 && a.mini <= 0) return 1;
	return 2;
}

int cmp(X a, X b) {
	if(grupo(a) < grupo(b)) {
		return 1;
	} else if(grupo(a) == grupo(b)) {
		if(grupo(a) == 0) {
			return a.id < b.id;
		} else if(grupo(a) == 1){
			if(a.mini != b.mini) return a.mini > b.mini;
			if(a.saldo != b.saldo) return a.saldo > b.saldo;
			return a.id < b.id;
		} else {
			if(a.saldo - a.mini != b.saldo - b.mini) {
				return a.saldo - a.mini > b.saldo - b.mini;
			} else {
				return a.id < b.id;
			}
		}
	} else {
		return 0;
	}
}

int main() {
	scanf("%d", &n);
	char aux[MAX];
	for(int i = 0; i < n; i++) {
		scanf("%s", aux);
		int qtd = 0, tam = 0, mini = 0, maxi = 0, abre = 0, fecha = 0, id = i+1;
		for(char *c = aux; *c; c++) {
			if(*c == '(') {
				qtd++;
				abre++;
			}
			else {
				qtd--;
				fecha++;
			}
			mini = min(mini, qtd);
			maxi = max(maxi, qtd);
			tam++;
		}

//X make_parenteses(int saldo, int mini, int tam,int id) {
		v[i] = make_parenteses(qtd, mini, tam, id);
	}
	sort(v, v+n, cmp);
	memset(pd, -1, sizeof(pd));
	int val = vamo(0, 0);
	printf("%d ", val);
	int k = 0;

	int pos = 0, acu = 0;
	vector<int> x;
	while(val && pos < n) {
		if(acu + v[pos].saldo >= 0 && acu + v[pos].mini >= 0) {
			int r = vamo(pos+1, acu + v[pos].saldo);
			if(r >= 0 && r + v[pos].tam == val) {
				x.push_back( v[pos].id );
				val -= v[pos].tam;
				acu += v[pos].saldo;
				pos++;
			} else {
				pos++;
			}
		} else {
			pos++;
		}
	}
	printf("%d\n", x.size());
	for(int i = 0; i < x.size(); i++) {
		printf("%d%c", x[i], i == x.size() - 1 ?  '\n' : ' ');
	}
	return 0;
}

Hyperrook (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <string.h>

using namespace std;

#define NMAX 64

typedef unsigned long long llu;

int n, q;
llu m, p;
llu A[NMAX][NMAX], B[NMAX][NMAX], C[NMAX][NMAX], I[NMAX][NMAX], ans[NMAX];

void matrix_cpy(llu dest[NMAX][NMAX], llu orig[NMAX][NMAX]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dest[i][j] = orig[i][j];
		}
	}
}

void matrix_mul(llu dest[NMAX][NMAX], llu a[NMAX][NMAX], llu b[NMAX][NMAX]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dest[i][j] = 0;
			for (int k = 0; k < n; k++) {
				dest[i][j]+= (a[i][k] * b[k][j]) % p;
				dest[i][j]%= p;
			}
		}
	}
}

void matrix_exp(int e) {
	if (e == 0) {
		matrix_cpy(B, I);
	} else {
		matrix_exp(e / 2);
		if (e % 2 == 0) {
			matrix_mul(C, B, B);
			matrix_cpy(B, C);
		} else {
			matrix_mul(C, B, B);
			matrix_mul(B, A, C);
		}
	}
}

int main() {
	int in[NMAX][NMAX];
	llu d;
	scanf("%d %llu %llu %llu %d", &n, &m, &d, &p, &q);
	for (int i = 0; i < q; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &in[i][j]);
		}
	}
	memset(A, 0, sizeof(A));
	memset(I, 0, sizeof(I));
	n++;
	for (int i = 0; i < n; i++) {
		I[i][i] = 1 % p;
		if (i-1 >= 0) {
			A[i][i-1] = (i * (m - 1)) % p;
		}
		A[i][i] = ((n - 1 - i) * (m - 2)) % p;
		if (i+1 < n) {
			A[i][i+1] = (n - 1 - i) % p;
		}
	}
	matrix_exp(d);
	for (int i = 0; i < n; i++) {
		ans[i] = B[i][n - 1];
	}
	for (int i = 0; i < q; i++) {
		for (int j = 0; j < q; j++) {
			int iguais = 0;
			for (int k = 0; k < n - 1; k++) {
				if (in[i][k] == in[j][k]) {
					iguais++;
				}
			}
			if (j != 0) {
				printf(" ");
			}
			printf("%llu", ans[iguais]);
		}
		printf("\n");
	}
	return 0;
}

Kingdom Inspection (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>

#define NMAX 131072

long long F[NMAX], G[NMAX];
long long N, p;

long long mul_mod(long long a, long long b) {
	return (a * b) % p;
}

int main() {
	scanf("%lld %lld", &N, &p);
	N--;
	F[1] = 0;
	G[1] = 1;
	for (int n = 2; n <= N; n++) {
		F[n] = mul_mod(n, mul_mod(mul_mod(2, n - 1), F[n-1]) + G[n-1]);
		G[n] = mul_mod(n, mul_mod(mul_mod(2, n) - 1, F[n-1]) + G[n-1]);
	}
	printf("%lld\n", F[N]);
	return 0;
}

The Most Complex Number (por [IME-USP] Isso é tudo pessoal)

#include <stdio.h>
#include <algorithm>

using namespace std;

typedef unsigned long long llu;

llu n;
int P[18] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 };

pair <llu,llu> ans;

void f(int idx, int maxexp, llu m, llu o) {
	if (o > ans.second || (o == ans.second && m < ans.first)) {
		ans = make_pair(m, o);
	}
	for (int exp = 1; exp <= maxexp && m <= n/P[idx]; exp++) {
		m*= P[idx];
		f(idx + 1, exp, m, o * (exp + 1));
	}
}

int main() {
	int tests;
	scanf("%d", &tests);
	while (tests--) {
		scanf("%llu", &n);
		ans = make_pair(1, 1);
		f(0, 63, 1, 1);
		printf("%llu %llu\n", ans.first, ans.second);
	}
	return 0;
}

Pakhom and the Gully (por SUDO)

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define EPS 1e-9

#define min(x,y) ((x) < (y) ? (x) : (y))

int cmpD( double x, double y = 0, double tol = EPS ) {
    return ( x <= y + tol ) ? ( x + tol < y ) ? -1 : 0 : 1;
}

double dist_pp(double x1, double y1, double x2, double y2) {
	return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

int sinal(int a) {
	return (a < 0) ? -1 : (a > 0) ? 1 : 0;
}

int prod_vet(int x1, int y1, int x2, int y2) {
	return x1*y2 - x2*y1;
}

int inside(int x1, int y1, int x2, int y2, int x3, int y3, int X, int Y) {
	//printf("%d %d %d\n",sinal(prod_vet(x1-x2,y1-y2,X-x2,Y-y2)),sinal(prod_vet(X-x2,Y-y2,x3-x2,y3-y2)),sinal(prod_vet(x1-x2,y1-y2,x3-x2,y3-y2)));
	return (sinal(prod_vet(x1-x2,y1-y2,X-x2,Y-y2)) > 0 && sinal(prod_vet(X-x2,Y-y2,x3-x2,y3-y2)) > 0 && sinal(prod_vet(x1-x2,y1-y2,x3-x2,y3-y2)) >= 0) || 
		   (sinal(prod_vet(x1-x2,y1-y2,X-x2,Y-y2)) < 0 && sinal(prod_vet(X-x2,Y-y2,x3-x2,y3-y2)) < 0 && sinal(prod_vet(x1-x2,y1-y2,x3-x2,y3-y2)) <= 0);
}

int seg_intersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
	return ((prod_vet(x1-x2,y1-y2,x3-x2,y3-y2) < 0 && prod_vet(x1-x2,y1-y2,x4-x2,y4-y2) > 0) || 
			(prod_vet(x1-x2,y1-y2,x3-x2,y3-y2) > 0 && prod_vet(x1-x2,y1-y2,x4-x2,y4-y2) < 0)) &&
		   ((prod_vet(x4-x3,y4-y3,x1-x3,y1-y3) < 0 && prod_vet(x4-x3,y4-y3,x2-x3,y2-y3) > 0) || 
			(prod_vet(x4-x3,y4-y3,x1-x3,y1-y3) > 0 && prod_vet(x4-x3,y4-y3,x2-x3,y2-y3) < 0));
}

int main() {
	int t;
	
	cin >> t;
	
	while (t--) {
		int x[5], y[5];
		double dist[5][5];
		
		for (int i=0; i < 5; i++) {
			for (int j=0; j < 5; j++) {
				dist[i][j] = 1000000.0;
			}
		}
		
		for (int i=0; i < 5; i++) {
			cin >> x[i] >> y[i];
			if (i > 2) {
				dist[i-1][i] = dist[i][i-1] = dist_pp(x[i],y[i],x[i-1],y[i-1]);
			}
		}
		
		if (prod_vet(x[4]-x[3],y[4]-y[3],x[2]-x[3],y[2]-y[3]) == 0) {
			double ans = 1000000.0;
			
			if (cmpD(dist_pp(x[2],y[2],x[3],y[3])+dist_pp(x[3],y[3],x[4],y[4]),dist_pp(x[2],y[2],x[4],y[4])) == 0) {
				// nothing
			}
			else if (cmpD(dist_pp(x[3],y[3],x[2],y[2])+dist_pp(x[2],y[2],x[4],y[4]),dist_pp(x[3],y[3],x[4],y[4])) == 0) {
				x[2] = x[3], y[2] = y[3];
			}
			else {
				x[4] = x[3], y[4] = y[3];
			}
			
			if (seg_intersect(x[0],y[0],x[1],y[1],x[2],y[2],x[4],y[4])) {
				ans = min( dist_pp(x[0],y[0],x[2],y[2])+dist_pp(x[1],y[1],x[2],y[2]), dist_pp(x[0],y[0],x[4],y[4])+dist_pp(x[1],y[1],x[4],y[4]) );
			}
			else {
				ans = dist_pp(x[0],y[0],x[1],y[1]);
			}
			
			printf("%.6lf\n",ans);
			
			continue;
		}
		
		for (int i=0; i < 5; i++) {
			for (int j=0; j < 5; j++) {
				if (!seg_intersect(x[i],y[i],x[j],y[j],x[3],y[3],x[4],y[4]) && !seg_intersect(x[i],y[i],x[j],y[j],x[2],y[2],x[3],y[3])) {
					dist[i][j] = dist_pp(x[i],y[i],x[j],y[j]);
				}
			}
		}
		
		for (int i=2; i < 5; i++) {
			if (cmpD(dist_pp(x[0],y[0],x[i],y[i])+dist_pp(x[1],y[1],x[i],y[i]),dist_pp(x[0],y[0],x[1],y[1])) == 0) {
				dist[0][1] = dist[1][0] = 1000000.0;
			}
		}
		
		if (inside(x[2],y[2],x[3],y[3],x[4],y[4],x[0],y[0]) != inside(x[2],y[2],x[3],y[3],x[4],y[4],x[1],y[1])) {
			//dist[0][3] = dist[3][0] = dist[1][3] = dist[3][1] = 1000000.0;
		}
		
		/*
		for (int i=0; i < 5; i++) {
			for (int j=0; j < 5; j++) {
				printf("%11.2lf",dist[i][j]);
			}
			puts("");
		}
		//*/
		
		for (int m=0; m < 5; m++) {
		for (int k=0; k < 5; k++) {
			for (int i=0; i < 5; i++) {
				for (int j=0; j < 5; j++) {
					if (i < 2 && j < 2 && k == 3 && inside(x[2],y[2],x[3],y[3],x[4],y[4],x[0],y[0]) != inside(x[2],y[2],x[3],y[3],x[4],y[4],x[1],y[1])) {
						
					}
					else {
						dist[i][j] = min( dist[i][j], dist[i][k]+dist[k][j] );
					}
				}
			}
		}
		}
		
		printf("%.6lf\n",dist[0][1]);
	}
	
    return 0;
}

Improbability Theory (por [ITA] Carteado)

#include<cstdio>
#include<vector>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;

const int maxn = 555;
vector<int> ladj[maxn];
int preorder[maxn],cfc[maxn];
int num_order,num_cfc,n,m;
stack<int> P,S;
void dfs_gabow(int v)
{
  preorder[v]=num_order++;
  P.push(v),S.push(v);
  for(vector<int>::iterator it=ladj[v].begin();it!=ladj[v].end();it++)
    {
      if(preorder[*it]==-1)dfs_gabow(*it);
      else if(cfc[*it]==-1)while(preorder[P.top()]>preorder[*it]) P.pop();
    }
  if(P.top()==v)
    {
      while(S.top()!=v){cfc[S.top()]=num_cfc;S.pop();}
      S.pop(),P.pop();
      cfc[v]=num_cfc++;
    }
}
void gabow()
{
  num_cfc=num_order=0;
  for(int i=0;i<n;i++)
    cfc[i]=preorder[i]=-1;
  for(int i=0;i<n;i++)
    if(preorder[i]==-1)dfs_gabow(i);
}
double prob[maxn];
double tempo[maxn];
vector<int> componente[maxn];
double esp_comp[maxn];
double prob_comp[maxn];
bool cooomp(int a,int b)
{
  return tempo[a]+(prob[a])*tempo[b] < tempo[b] + (prob[b])*tempo[a]; 
}
void calc(int c)
{
  sort(componente[c].begin(),componente[c].end(),cooomp);
  prob_comp[c]=1;
  for(int i=0;i<componente[c].size();i++)
    prob_comp[c]*=prob[componente[c][i]];
  esp_comp[c]=0;
  for(int i=componente[c].size()-1;i>=0;i--)
    {
      esp_comp[c] = (prob[componente[c][i]])*esp_comp[c]+tempo[componente[c][i]]; 
    }
}

//vector<int> ladj2[maxn];
bool grafo2[maxn][maxn];
bool foi[maxn];
pair<double,double>saida[maxn];
pair<double,double> go(int a)
{
  if(foi[a])
    return saida[a];
  foi[a]=true;
  double prob=1.0;
  for(int i=0;i<num_cfc;i++)
    {
      if(grafo2[a][i])
	prob*=prob_comp[i];
    }
  //x printf("%d %lf %lf %d\n",a,esp_comp[a],prob,ladj2[a].size());
  saida[a]=make_pair(esp_comp[a],prob);
  return saida[a];
}
int main ()
{
  while(scanf("%d",&n)==1)
    {
      if(n==0)break;
      for(int i=0;i<n;i++)
	ladj[i].clear();
      for(int i=0;i<n;i++)
	{
	  int k,t;
	  scanf("%lf %lf %d",&tempo[i],&prob[i],&k);
	  for(int j=0;j<k;j++)
	    {
	      scanf("%d",&t);
	      ladj[t-1].push_back(i);
	    }
	}
      gabow();
      for(int i=0;i<num_cfc;i++)
	componente[i].clear();
      memset(grafo2,false,sizeof(grafo2));
      for(int i=0;i<n;i++)
	{
	  componente[cfc[i]].push_back(i);
	  for(int j=0;j<ladj[i].size();j++)
	    {
	      if(cfc[ladj[i][j]]!=cfc[i])//sem aresta pra ele msm
		grafo2[cfc[ladj[i][j]]][cfc[i]]=true;
	    }
	}
      for(int k=0;k<num_cfc;k++)
	for(int i=0;i<num_cfc;i++)
	  for(int j=0;j<num_cfc;j++)
	    grafo2[i][j]=grafo2[i][j]|(grafo2[i][k]&grafo2[k][j]);

      for(int i=0;i<num_cfc;i++)
	{
	  foi[i]=0;
	  calc(i);
	  //printf("%lf %lf\n",esp_comp[i],prob_comp[i]);
	}

      double ret=0;
      for(int i=0;i<num_cfc;i++)
	{
	  ret+=(go(i).first)*(go(i).second);
	}
      printf("%.3f\n",ret);
      n=0;
    }
  return 0;
}

Tree 2 (por [IME-USP] Isso é tudo pessoal)

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

#define N 20000
#define L 20

int dist[N][L];
int pai[N][L];
int prof[N];
int A,B;
vector<int> adj[N];

void monta(int v, int p, int d) {
	pai[v][0] = p;
	dist[v][0] = 1;
	prof[v] = d;
	for(int i = 1; i < L; i++) {
		int pp = pai[v][i-1];
		pai[v][i] = pai[pp][i-1];
		dist[v][i] = dist[v][i-1] + dist[pp][i-1];
	}
	for(vector<int>::iterator it = adj[v].begin(); it != adj[v].end(); it++) {
		if(*it != p) {
			monta(*it, v, d+1);
		}
	}
}

void monta_LCA() {
	for(int i = 0; i < L; i++) {
		pai[0][i] = 0;
		dist[0][i] = 0;
	}
	prof[0] = 0;
	for(int i = 0; i < adj[0].size(); i++) {
		monta(adj[0][i], 0, 1);
	}
}

pair<int, pair<int,int> > ajusta_nivel(int a, int b) {
	int d = 0;
	while(prof[a] != prof[b]) {
		for(int i = L-1; i >= 0; i--) {
			if(prof[a] > prof[b]) {
				int aux = pai[a][i];
				if(prof[aux] >= prof[b]) {
					d += dist[a][i];
					a = aux;
					break;
				}
			} else {
				int aux = pai[b][i];
				if(prof[aux] >= prof[a]) {
					d += dist[b][i];
					b = aux;
					break;
				}
			}
		}
	}
	return make_pair(d, make_pair(a,b));
}

int LCA(int a, int b) {
	pair< int , pair<int,int> > pp = ajusta_nivel(a,b);
	a = pp.second.first;
	b = pp.second.second;
	while(a != b) {
		for(int i = 1; i < L; i++) {
			if(pai[a][i] == pai[b][i]) {
				a = pai[a][i-1];
				b = pai[b][i-1];
				break;
			}
		}
	}
	return a;
}

int distancia_lca(int a, int b) {
	pair< int , pair<int,int> > pp = ajusta_nivel(a,b);
	int d = pp.first;
	a = pp.second.first;
	b = pp.second.second;
	while(a != b) {
		for(int i = 1; i < L; i++) {
			if(pai[a][i] == pai[b][i]) {
				d += dist[a][i-1];
				d += dist[b][i-1];
				a = pai[a][i-1];
				b = pai[b][i-1];
				break;
			}
		}
	}
	return d;
}

int busca_sobe(int a, int b, int k) {
	while(a != b && k) {
		for(int i = 1; i < L; i++) {
			if(  dist[a][i] >= k) {
				k -= dist[a][i-1];
				a = pai[a][i-1];
				break;
			}
		}
	}
	return a;
}


int busca(int a, int b, int k) {
	int lca = LCA(a,b);
	if(distancia_lca(a, lca) == k) return lca;

	if(distancia_lca(a, lca) >= k) {
		return busca_sobe(a, lca, k);
	} else {
		k -= distancia_lca(a, lca);
		int tot = distancia_lca(b, lca);
		return busca_sobe(b, lca, tot - k);
	}
}

/*
int opa[N];

int bruta(int a, int b) {
	memset(opa, -1, sizeof(opa));
	opa[a] = 0;
	queue<int> fila;
	fila.push(a);
	while(!fila.empty()) {
		a = fila.front(); fila.pop();
		for(vector<int>::iterator it = adj[a].begin(); it != adj[a].end(); it++) {
			if(opa[*it] == -1) {
				opa[*it] = opa[a] + 1;
				fila.push(*it);
			}
		}
	}
	return opa[b];
}
*/

int main() {
	int n,q;
	scanf("%d %d", &n, &q);
	for(int i = 0; i < n; i++) {
		adj[i].clear();
	}
	for(int i = 0; i < n-1; i++) {
		int a,b;
		scanf("%d %d", &a, &b);
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	queue<int> fila;
	int last;
	fila.push(0);
	memset(pai, 0, sizeof(pai));
	pai[0][0] = 1;
	while(!fila.empty()) {
		last = fila.front(); fila.pop();
		for(vector<int>::iterator it = adj[last].begin(); it != adj[last].end(); it++) {
			if( !pai[*it][0] ) {
				pai[*it][0] = 1;
				fila.push(*it);
			}
		}
	}
	int prim;
	fila.push(last);
	memset(pai, 0, sizeof(pai));
	pai[last][0] = 1;
	while(!fila.empty()) {
		prim = fila.front(); fila.pop();
		for(vector<int>::iterator it = adj[prim].begin(); it != adj[prim].end(); it++) {
			if( !pai[*it][0] ) {
				pai[*it][0] = 1;
				fila.push(*it);
			}
		}
	}

	A = last; B = prim;
	monta_LCA();


	/*
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			printf("LCA %d %d = %d, com dist = %d\n", i+1, j+1, LCA(i,j)+1, distancia_lca(i,j));
		}
	}
	return 0;
	*/
		
	for(int i = 0; i < q; i++) {
		int v,k;
		scanf("%d %d", &v, &k);
		v--;
		if(distancia_lca(v, A) >= k) {
			printf("%d\n", busca(v, A, k) + 1);
		//	printf("DISTA %d %d = %d, k = %d\n", v, busca(v, A, k), bruta(v, busca(v,A,k)), k);
			continue;
		} 

		if(distancia_lca(v, B) >= k) {
			printf("%d\n", busca(v, B, k) + 1);
		//	printf("DISTA %d %d = %d, k = %d\n", v, busca(v, B, k), bruta(v, busca(v,B,k)), k);
			continue;
		} 

		printf("0\n");
	}

	return 0;
}

Fighting against a Polygonal Monster (por [ITA] Carteado)

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

#define all(v) (v).begin(), (v).end()

const double eps = 1e-9;

struct point;

inline double dot(const point a, const point b);
inline double cross(const point a, const point b);
inline double norm(const point p);

struct point
{
  double x, y;
  inline point operator+(const point o) const { return (point){x + o.x, y + o.y}; }
  inline point operator-(const point o) const { return (point){x - o.x, y - o.y}; }
  inline point operator*(const double m) const { return (point){x*m, y*m}; }
  inline point operator/(const double m) const { return (point){x/m, y/m}; }
  inline point normalize() const { return *this / norm(*this); }
  inline point rotate(const double angle) const 
  { return (point){ x * cos(angle) - y * sin(angle), y * cos(angle) + x * sin(angle) }; }
};

inline double dot(const point a, const point b) { return a.x*b.x + a.y*b.y; }
inline double cross(const point a, const point b) { return a.x*b.y - a.y*b.x; }
inline double norm(const point p) { return sqrt(dot(p, p)); }

int N;

bool radial_lt(const point a, const point b)
{
  double anga = atan2(a.y, a.x), angb = atan2(b.y, b.x);
  return anga < angb - eps;
}

double pointlinedist(const point p, const point a, const point b)
{
  return fabs(cross(a - p, b - p)) / norm(b - a);
}

bool between(const point p, const point a, const point b)
{
  return dot(p - a, b - a) > eps && dot(p - b, a - b) > eps;
}

point project(const point p, const point q)
{
  return q * dot(p, q) / dot(q, q);
}

point project(const point p, const point a, const point b)
{
  return project(p - a, b - a) + a;
}

int main()
{
  int ncase = 0;
  while (scanf(" %d", &N), N)
    {
      double R;
      scanf(" %lf", &R);
      vector<point> points;
      for (int i=0; i<N; ++i)
	{
	  point p;
	  scanf(" %lf %lf", &p.x, &p.y);
	  points.push_back(p);
	}

      sort(all(points), radial_lt);
      
      double ll = 0, rr = 10000;
      for (int iter=0; iter<100; ++iter)
	{
	  double r = (ll + rr) / 2;
	  
	  vector<point> morepoints(all(points));
	  for (int i=0; i<(int)points.size(); ++i)
	    {
	      point p = points[i], q = points[(i+1)%(int)points.size()];
	      double d;
	      if ( (d = pointlinedist((point){0, 0}, p, q)) < r - eps)
		{
		  point Oprime = project((point){0, 0}, p, q);
		  double m = sqrt(r*r - d*d);
		  for (int sign=-1; sign<=1; sign+=2)
		    {
		      point x = Oprime + (q - p).normalize()*m*sign;
		      //printf("OX: %f, r: %f\n", norm(x), r);
		      if (between(x, p, q))
			morepoints.push_back(x);
		    }
		}
	    }

	  sort(all(morepoints), radial_lt);

	  // 	  printf("morepoints:\n");
	  // 	  for (int i=0; i<(int)morepoints.size(); ++i)
	  // 	    printf("%f %f\n", morepoints[i].x, morepoints[i].y);

	  double area = 0;
	  for (int i=0; i<(int)morepoints.size(); ++i)
	    {
	      point p = morepoints[i], q = morepoints[(i+1)%(int)morepoints.size()];
	      // 	      printf("p = %f %f, q = %f %f\n", p.x, p.y, q.x, q.y);
	      double delta;
	      if ( norm((p + q)/2) < r )
		{
		  delta = cross(p, q) / 2;
		  // 		  printf("triangular area: %f\n", delta);
		}
	      else
		{
		  delta = acos(dot(p, q) / norm(p) / norm(q)) / 2 * r * r;
		  // 		  printf("sector area: %f\n", delta);
		}
	      area += delta;
	    }

	  //printf("r: %.2f, area: %.2f\n", r, area);

	  if (area > R)
	    rr = r;
	  else
	    ll = r;
	}

      printf("Case %d: %.2f\n", ++ncase, ll);
    }

  return 0;
}