Untitled

A:

#include <bits/stdc++.h>

using namespace std;

void dfs(int row, int col, vector<vector<char>> &map, vector<vector<bool>> &visited) {
    visited[row][col] = true;
    int n = map.size();
    int m = map[0].size();
    
    for (int i = -1; i <= 1; i++) {
            int newRow = row + i;
            if (newRow >= 0 && newRow < n && col >= 0 && col < m
            && !visited[newRow][col] && map[newRow][col] == '.') {
                dfs(newRow, col, map, visited);
            }
    }
    
    for (int j = -1; j <= 1; j++) {
        int newCol = col + j;
        
        if (row >= 0 && row < n && newCol >= 0 && newCol < m
        && !visited[row][newCol] && map[row][newCol] == '.') {
            dfs(row, newCol, map, visited);
        }
    }
}

int countRooms(int n, int m, vector<vector<char>> &map, vector<vector<bool>> &visited) {
    int cnt = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && map[i][j] == '.') {
                dfs(i, j, map, visited);
                cnt++;
            }
        }
    }
    
    return cnt;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<char>> map(n, vector<char>(m));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
    
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    
    int ans = countRooms(n, m, map, visited);
    
    cout << ans << endl;

    return 0;
}


B:

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<tuple<int, int, int>> edges;
    vector<int> dist(n + 1, 30000);


    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back(make_tuple(u, v, w));
    }

    dist[1] = 0;


    for (int i = 1; i <= n - 1; i++) {
        for (const auto& edge : edges) {
            int u, v, w;
            tie(u, v, w) = edge;
            if (dist[u] < 30000) {
                dist[v] = min(dist[v], dist[u] + w);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << dist[i] << " ";
    }
    cout << endl;

    return 0;
}


D:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    unordered_set<string> umap;
    unordered_set<string> umap2;
    
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (s[0] == '!') {
            umap2.insert(s.substr(1));
        } else {
            umap.insert(s);
        }
    }
    
    string ans = "satisfiable";
    
    for (auto it: umap) {
        if (umap2.find(it) != umap2.end()) {
            ans = it;
            break;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}


G:

#include <bits/stdc++.h>
using namespace std;

long printResult(long child, long position) {
    if (child == 1) return 1;

    if (position <= (child + 1) / 2) {
        if (2 * position > child) {
            return (2 * position) % child;
        } else {
            return 2 * position;
        }
    } else {
        long temp = printResult(child / 2, position - (child + 1) / 2);
        if (child % 2 == 1)
            return 2 * temp + 1;
        else
            return 2 * temp - 1;
    }
}

int main() {
    long q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        long child, position;
        cin >> child >> position;
        cout << printResult(child, position) << endl;
    }
    return 0;
}


H:

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

void findPostorder(int preStart, int inStart, int inEnd,
                   vector<int>& preorder, vector<int>& inorder,
                   unordered_map<int, int>& inIndexMap) {
   
    if (inStart > inEnd) return;
   
    int root = preorder[preStart];
    int rootIndex = inIndexMap[root];
    int leftSubtreeSize = rootIndex - inStart;
   
    findPostorder(preStart + 1, inStart, rootIndex - 1, preorder, inorder, inIndexMap);
   
    findPostorder(preStart + leftSubtreeSize + 1, rootIndex + 1, inEnd, preorder, inorder, inIndexMap);
   
    cout << root << " ";
}

int main() {
    int n;
    cin >> n;
   
    vector<int> preorder(n), inorder(n);
    unordered_map<int, int> inIndexMap;
   
    for (int i = 0; i < n; i++) {
        cin >> preorder[i];
    }
   
    for (int i = 0; i < n; i++) {
        cin >> inorder[i];
        inIndexMap[inorder[i]] = i;
    }
   
    findPostorder(0, 0, n - 1, preorder, inorder, inIndexMap);
   
    return 0;
}


I:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {
  while (b != 0) {
    ll temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}

pair<ll, ll> parseFraction(string s) {
  int divPos = s.find('/');
  ll num = stoll(s.substr(0, divPos));
  ll den = stoll(s.substr(divPos + 1));
  return {num, den};
}

pair<ll, ll> simplify(ll num, ll den) {
  ll g = gcd(abs(num), abs(den));
  return {num / g, den / g};
}

int main() {
  string x, y;
  char z;
  while (cin >> x) {
    cin >> z >> y;

    pair<ll, ll> frac1 = parseFraction(x);
    pair<ll, ll> frac2 = parseFraction(y);

    ll numX = frac1.first, denX = frac1.second;
    ll numY = frac2.first, denY = frac2.second;
    ll commonDen = denX * denY;
    numX *= denY;
    numY *= denX;

    ll numSum = 0;
    if (z == '+') {
      numSum = numX + numY;
    } else if (z == '-') {
      numSum = numX - numY;
    }

    pair<ll, ll> res = simplify(numSum, commonDen);

    if (res.second < 0) {
      res.first = -res.first;
      res.second = -res.second;
    }

    cout << res.first << "/" << res.second << endl;
  }

  return 0;
}