Seletiva IOI 2017

danone.cpp

// Ivan Carvalho
// Danone - Seletiva IOI - OBI 2017
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2*1e6 + 10;
typedef long long ll;
typedef pair<ll,ll> ii;
vector<ii> grafo[MAXN];
int processado[MAXN],raiz[MAXN],pai[MAXN],peso[MAXN],N,Q;
int e1[MAXN],e2[MAXN],e3[MAXN];
ll acumulado[MAXN];
int find(int x){
	if(x == pai[x]) return x;
	return pai[x] = find(pai[x]);
}
void join(int x,int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	if(peso[x] < peso[y]) swap(x,y);
	pai[y] = x;
	peso[x] += peso[y]; 
}
void processa(int ini){
	queue<ii> bfs;
	bfs.push(ii(0,ini));
	processado[ini] = 1;
	while(!bfs.empty()){
		ii davez = bfs.front();
		bfs.pop();
		ll v = davez.second, d = davez.first;
		raiz[v] = ini;
		acumulado[v] = d;
		for(int i = 0;i<grafo[v].size();i++){
			ll u = grafo[v][i].first, w = grafo[v][i].second;
			if(processado[u]) continue;
			processado[u] = 1;
			bfs.push(ii(d + w,u));
		}
	}
}
int main(){
	scanf("%d %d",&N,&Q);
	for(int i = 1;i<=Q;i++){
		char op;
		scanf(" %c",&op);
		if(op == 'L'){
			int a,b,peso;
			scanf("%d %d %d",&a,&b,&peso);
			b++;
			grafo[a].push_back(ii(b,peso));
			grafo[b].push_back(ii(a,-peso));
			e1[i] = 1;
			e2[i] = a;
			e3[i] = b;
		}
		else{
			int a,b;
			scanf("%d %d",&a,&b);
			e1[i] = 2;
			e2[i] = a;
			e3[i] = b + 1;
		}
	}
	for(int i = 1;i<=N+1;i++){
		pai[i] = i;
		peso[i] = 1;
	}
	for(int i = 1;i<=N+1;i++){
		if(processado[i]) continue;
		processa(i);
	}
	for(int i = 1;i<=Q;i++){
		if(e1[i] == 1){
			join(e2[i],e3[i]);
		}
		else{
			if(find(e2[i]) != find(e3[i])) printf("Esquecido\n");
			else printf("%lld\n",acumulado[e3[i]] - acumulado[e2[i]]);
		}
	}
	return 0;
}