Ronda Codeforces 911 (Div. 2)

A. Cubierto con Agua

，，，mc agua infinita

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void resolver(){
    int tamanio;
    string cadena;
    cin >> tamanio >> cadena;
    cadena = " " + cadena + " ";
    int contador = 0;
    
    for(int posicion = 2; posicion <= tamanio - 1; posicion++){
        if(cadena[posicion] == '.' && cadena[posicion-1] == '.' && cadena[posicion+1] == '.'){
            cout << 2 << endl;
            return;
        }
        if(cadena[posicion] == '.') contador++;
    }
    
    if(tamanio != 1) contador += (cadena[1] == '.') + (cadena[tamanio] == '.');
    else contador += (cadena[1] == '.');
    
    cout << contador << endl;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int casos = 1;
    cin >> casos;
    while(casos--) resolver();
    return 0;
}

B. Laura y Operaciones

#include <iostream>
#include <vector>
using namespace std;

void resolver(){
    int valor1, valor2, valor3;
    vector<int> resultados;
    cin >> valor1 >> valor2 >> valor3;
    
    int diferencia = abs(valor2 - valor3);
    if(diferencia % 2 != 0) resultados.push_back(0);
    else resultados.push_back(1);
    
    diferencia = abs(valor1 - valor3);
    if(diferencia % 2 != 0) resultados.push_back(0);
    else resultados.push_back(1);
    
    diferencia = abs(valor1 - valor2);
    if(diferencia % 2 != 0) resultados.push_back(0);
    else resultados.push_back(1);
    
    for(auto elemento : resultados) cout << elemento << " ";
    cout << endl;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int casos = 1;
    cin >> casos;
    while(casos--) resolver();
    return 0;
}

C

Más fácil que B

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

const int MAX = 3e5 + 10;
int izquierdo[MAX], derecho[MAX];
longitud[MAX];
int nodos;
string estructura;
void recorrer(int nodo){
    if(izquierdo[nodo] == 0 && derecho[nodo] == 0) return;
    
    if(estructura[nodo] == 'L'){
        longitud[izquierdo[nodo]] = longitud[nodo];
        longitud[derecho[nodo]] = longitud[nodo] + 1;
    }
    else if(estructura[nodo] == 'R'){
        longitud[derecho[nodo]] = longitud[nodo];
        longitud[izquierdo[nodo]] = longitud[nodo] + 1;
    }
    else {
        longitud[derecho[nodo]] = longitud[nodo] + 1;
        longitud[izquierdo[nodo]] = longitud[nodo] + 1;
    }
    
    if(izquierdo[nodo] != 0) recorrer(izquierdo[nodo]);
    if(derecho[nodo] != 0) recorrer(derecho[nodo]);
}

void resolver(){
    cin >> nodos;
    cin >> estructura;
    estructura = " " + estructura;
    vector<int> hojas;
    
    for(int i = 1; i <= nodos; i++){
        cin >> izquierdo[i] >> derecho[i];
        if(izquierdo[i] == 0 && derecho[i] == 0) hojas.push_back(i);
    }
    
    longitud[1] = 0;
    recorrer(1);
    
    long long respuesta = 1e18;
    for(auto nodo : hojas) respuesta = min(respuesta, longitud[nodo]);
    cout << respuesta << endl;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int casos = 1;
    cin >> casos;
    while(casos--) resolver();
    return 0;
}

D

Tengo la sensación de que si lo escribo otra vez no sabré cómo hacerlo.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 1e5 + 10;
int valores[MAX];
int total;

void resolver(){
    vector<vector<int>> factores(MAX + 10);
    for(int i = 1; i <= MAX; i++)
        for(int j = i; j <= MAX; j += i)
            factores[j].push_back(i);

    cin >> total;
    for(int i = 1; i <= total; i++) cin >> valores[i];
    sort(valores + 1, valores + 1 + total);

    vector<vector<int>> contador(MAX + 10);
    for(int i = 1; i <= total; i++)
        for(auto factor : factores[valores[i]])
            contador[factor].push_back(total - i);

    vector<int> f(MAX + 10);
    vector<int> g(MAX + 10);
    
    for(int i = 1; i <= MAX; i++)
        for(int j = 0; j < contador[i].size(); j++)
            f[i] += contador[i][j] * j;
    
    long long respuesta = 0;
    for(int i = MAX; i > 0; i--){
        g[i] = f[i];
        for(int j = i * 2; j <= MAX; j += i) g[i] -= g[j];
        respuesta += g[i] * i;
    }
    cout << respuesta << endl;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int casos = 1;
    cin >> casos;
    while(casos--) resolver();
    return 0;
}

E

Reducir componentes fuertemnete conexos + topológico

md olvidé inicializar G, buscando errores durante mucho tiempo.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 2e5 + 10;
vector<int> grafo[MAX];
int valores[MAX];
int nodos, aristas;
int dfn[MAX], low[MAX], reloj;
bool visitado[MAX];
int padre[MAX], tamano[MAX], suma[MAX], grado[MAX];
int total;
vector<pair<int, int>> dp(MAX);
vector<int> camino;

void tarjin(int nodo){
    dfn[nodo] = low[nodo] = ++reloj;
    visitado[nodo] = true;
    camino.push_back(nodo);
    
    for(auto vecino : grafo[nodo]){
        if(!dfn[vecino]){
            tarjin(vecino);
            low[nodo] = min(low[vecino], low[nodo]);
        }
        else if(visitado[vecino]) low[nodo] = min(low[nodo], dfn[vecino]);
    }
    
    if(dfn[nodo] == low[nodo]){
        int actual;
        total++;
        do{
            actual = camino.back();
            camino.pop_back();
            visitado[actual] = false;
            tamano[total]++;
            padre[actual] = total;
            suma[total] += valores[actual];
        }while(actual != nodo);
    }
}

void resolver(){
    reloj = total = 0;
    cin >> nodos >> aristas;
    
    for(int i = 1; i <= nodos; i++){
        cin >> valores[i];
        dfn[i] = low[i] = 0;
        suma[i] = grado[i] = 0;
        dp[i].first = dp[i].second = 0;
        padre[i] = i;
        tamano[i] = 0;
        visitado[i] = false;
        grafo[i].clear();
    }
    
    vector<pair<int, int>> aristasLista(aristas);
    for(auto &[origen, destino] : aristasLista){
        cin >> origen >> destino;
        grafo[origen].push_back(destino);
    }
    
    for(int i = 1; i <= nodos; i++)
        if(!dfn[i])
            tarjin(i);

    for(int i = 1; i <= nodos; i++) grafo[i].clear();
    
    for(auto [origen, destino] : aristasLista){
        if(padre[origen] == padre[destino]) continue;
        grafo[padre[origen]].push_back(padre[destino]);
        grado[padre[destino]]++;
    }

    queue<int> cola;
    for(int i = 1; i <= total; i++){
        if(grado[i] == 0){
            cola.push(i);
            dp[i].first = tamano[i];
            dp[i].second = suma[i];
        }
    }
    
    while(!cola.empty()){
        int nodo = cola.front(); cola.pop();
        for(auto vecino : grafo[nodo]){
            if(dp[nodo].first + tamano[vecino] > dp[vecino].first){
                dp[vecino].first = dp[nodo].first + tamano[vecino];
                dp[vecino].second = dp[nodo].second + suma[vecino];
            }
            else if(dp[nodo].first + tamano[vecino] == dp[vecino].first){
                dp[vecino].second = min(dp[nodo].second + suma[vecino], dp[vecino].second);
            }
            
            if(--grado[vecino] == 0) cola.push(vecino);
        }
    }
    
    int longitud = 0;
    int totalSuma = 0;
    for(int i = 1; i <= nodos; i++){
        if(dp[i].first > longitud){
            longitud = dp[i].first;
            totalSuma = dp[i].second;
        }
        else if(dp[i].first == longitud)
            totalSuma = min(totalSuma, dp[i].second);
    }
    cout << longitud << " " << totalSuma << endl;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int casos = 1;
    cin >> casos;
    while(casos--) resolver();
    return 0;
}