个人ACM模板

Windows - build.bat

@echo off
set exe=.\output\%~n1.exe
if not exist output mkdir output
g++ %1 -o %exe% -std=c++17 -Wall -Wextra -g3 -O2 -D_GLIBCXX_DEBUG && (
    echo [build done to %exe%]
    %exe%
)

#include <bits/stdc++.h>

using i64 = long long;

#define LOG(...) std::cerr << "Line[" << __LINE__ << "]: " << __VA_ARGS__ << std::endl;
#define LOGV(_vec, _size) std::cerr << #_vec << " = " << '['; for (int _i = 0; _i < (_size); _i++) { std::cerr << (_vec)[_i]; if (_i != (_size) - 1) std::cerr << ", "; } std::cerr << ']' << std::endl;

void solve() {}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int t; std::cin >> t; while (t--) solve();
    return 0;
}

using i64 = long long;
i64 binpow(i64 a, i64 b)
{
    // a %= m;
    i64 res = 1;
    while (b > 0) {
        if (b & 1) res = res * a; // % m;
        a = a * a; // % m;
        b >>= 1;
    }
    return res;
}

bool isPrime(int num)
{
    if (num == 1) return 0;
    if (num == 2 || num == 3) return 1;
    if (num % 6 != 1 && num % 6 != 5) return 0;
    int tmp = sqrt(num);
    for (int i = 5; i <= tmp; i += 6)
        if (num % i == 0 || num % (i + 2) == 0) return 0;
    return 1;
}

void best()
{
    int N, M; std::cin >> N >> M;
    std::vector map(N + 1, std::vector<int>(N + 1, 0));
    std::vector diff(N + 2, std::vector<int>(N + 2, 0));
    for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) std::cin >> map[i][j];

    while (M--) {
        int x1, x2, y1, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        diff[x1][y1]++;
        diff[x1][y2 + 1]--;
        diff[x2 + 1][y1]--;
        diff[x2 + 1][y2 + 1]++;
    }
//  修改
//  ###+@@@-
//  ###@@@@#
//  ###-###+
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            diff[i][j] += diff[i - 1][j];

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            diff[i][j] += diff[i][j - 1];

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            std::cout << diff[i][j] + map[i][j] << ' ';
        }
        std::cout << '\n';
    }
}

template<typename InfoT, typename TagT>
class SGT {
public:
    struct node {
        InfoT info = InfoT();
        TagT tag = TagT();
    };
    std::vector<node> tree;
    int size;

    inline int lson(int p) { //* 左子节点
        return p << 1;
    }

    inline int rson(int p) { //* 右子节点
        return p << 1 | 1;
    }

    void addTag(int p, int curL, int curR, const TagT& delta) { //* 给代表[l,r]区间的Info打Tag
        //LOG("taged: " << curL << ',' << curR << " delta:" << delta)
        tree[p].tag.applyTo(tree[p].info, curL, curR, delta);
    }

    void push_up(int p) { //*用子节点Info更新父节点
        tree[p].info = tree[lson(p)].info.mergeWith(tree[rson(p)].info);
    }

    void push_down(int p, int curL, int curR) { //* 下传Tag
        if (!tree[p].tag.isVaild()) return;
        int mid = (curL + curR) >> 1;
        addTag(lson(p), curL, mid, tree[p].tag);
        addTag(rson(p), mid + 1, curR, tree[p].tag);
        tree[p].tag = TagT();
    }
    
    template<class T>
    SGT(std::vector<T>& source) {
        size = source.size() - 1;
        int bottom = 1;
        while (bottom < size) bottom <<= 1;
        tree.resize(bottom << 1);
        auto build = [&](auto&& self, int p, int curL, int curR) -> void {
            if (curL == curR) {
                tree[p].info = source[curL];
                return;
            }
            int mid = (curL + curR) >> 1;
            self(self, lson(p), curL, mid);
            self(self, rson(p), mid + 1, curR);
            push_up(p);
        };
        build(build, 1, 1, size);
    }
    
    InfoT query(int L, int R) {
        auto search = [&](auto&& self, int p, int curL, int curR) -> InfoT {
            node& cur = tree[p];
            if (L <= curL && curR <= R) return cur.info;
            push_down(p, curL, curR);
            InfoT res = InfoT();
            int mid = (curL + curR) >> 1; //? [curL, mid], [mid+1, curR]中一定有至少一个与[L, R]有交集
            if (L <= mid) res = res.mergeWith(self(self, lson(p), curL, mid));
            if (R >= mid + 1) res = res.mergeWith(self(self, rson(p), mid + 1, curR));
            return res;
        };
        return search(search, 1, 1, size);
    }

    void modify(int L, int R, const TagT& delta) {
        auto update = [&](auto&& self, int p, int curL, int curR) -> void {
            //LOG(curL << ',' << curR)
            if (L <= curL && curR <= R) {
                addTag(p, curL, curR, delta);
                return;
            }
            push_down(p, curL, curR);
            int mid = (curL + curR) >> 1;
            if (L <= mid) self(self, lson(p), curL, mid);
            if (R >= mid + 1) self(self, rson(p), mid + 1, curR);
            push_up(p);
        };
        update(update, 1, 1, size);
    }
};

struct Info {
    i64 val;
    Info() : val(0) {} // 初始化（重置时候用）
    Info(i64 v) : val(v) {} // 从其他类型转换（Build时候用）
    Info mergeWith(const Info& other) const { // 合并操作
        return Info(val + other.val);
    }
};

struct Tag {
    i64 add;
    Tag() : add(0) {} // 初始化（重置时候用）
    Tag(i64 d) : add(d) {} // 从其他类型转换（Modify时候用）
    bool isVaild() const { // tag是否生效
        return add != 0;
    }
    void applyTo(Info& info, int l, int r, const Tag& delta) { // 对代表[l,r]区间的info打上tag
        add += delta.add;
        info.val += delta.add * (r - l + 1);
    }
};

void solve()
{
    int N, M, S; // 点 边 出发点
    std::cin >> N >> M >> S;
    std::vector<std::vector<std::pair<int, int>>> graph(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v, len;
        std::cin >> u >> v >> len;
        graph[u].emplace_back(v, len);
        //graph[v].to.emplace_back(u, len);
    }

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> pq;
    std::vector<int> dis(N + 1, INT_MAX);
    dis[S] = 0;
    pq.emplace(0, S);
    while(!pq.empty()) {
        auto [d, i] = pq.top();
        pq.pop();
        if (d != dis[i]) continue;

        for (auto [nid, cost] : graph[i]) {
            if (dis[nid] > dis[i] + cost) {
                dis[nid] = dis[i] + cost;
                pq.emplace(dis[nid], nid);
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        std::cout << dis[i] << ' ';
    }
}

参考https://www.cnblogs.com/Cattle-Horse/p/16637943.html

template <typename T>
concept CanBit = requires(T x) { x >>= 1; };
template <int MOD>
struct modint {
    int val;
    static int norm(const int& x) { return x < 0 ? x + MOD : x; }
    static constexpr int get_mod() { return MOD; }
    modint inv() const {
        assert(val);
        int a = val, b = MOD, u = 1, v = 0, t;
        while (b > 0) t = a / b, std::swap(a -= t * b, b), std::swap(u -= t * v, v);
        assert(b == 1);
        return modint(u);
    }
    modint() : val(0) {}
    modint(const int& m) : val(norm(m)) {}
    modint(const i64& m) : val(norm(m % MOD)) {}
    modint operator-() const { return modint(norm(-val)); }
    bool operator==(const modint& o) { return val == o.val; }
    bool operator<(const modint& o) { return val < o.val; }
    modint& operator+=(const modint& o) { return val = (1LL * val + o.val) % MOD, *this; }
    modint& operator-=(const modint& o) { return val = norm(1LL * val - o.val), *this; }
    modint& operator*=(const modint& o) { return val = static_cast<int>(1LL * val * o.val % MOD), *this; }
    modint& operator/=(const modint& o) { return *this *= o.inv(); }
    modint& operator^=(const modint& o) { return val ^= o.val, *this; }
    modint& operator>>=(const modint& o) { return val >>= o.val, *this; }
    modint& operator<<=(const modint& o) { return val <<= o.val, *this; }
    modint operator-(const modint& o) const { return modint(*this) -= o; }
    modint operator+(const modint& o) const { return modint(*this) += o; }
    modint operator*(const modint& o) const { return modint(*this) *= o; }
    modint operator/(const modint& o) const { return modint(*this) /= o; }
    modint operator^(const modint& o) const { return modint(*this) ^= o; }
    modint operator>>(const modint& o) const { return modint(*this) >>= o; }
    modint operator<<(const modint& o) const { return modint(*this) <<= o; }
    friend std::istream& operator>>(std::istream& is, modint& a) {
        i64 v;
        return is >> v, a.val = norm(v % MOD), is;
    }
    friend std::ostream& operator<<(std::ostream& os, const modint& a) { return os << a.val; }
    friend std::string tostring(const modint& a) { return std::to_string(a.val); }
    template <CanBit T>
    friend modint qpow(const modint& a, const T& b) {
        assert(b >= 0);
        modint x = a, res = 1;
        for (T p = b; p; x *= x, p >>= 1)
            if (p & 1) res *= x;
        return res;
    }
};

防止hash碰撞
原文链接：https://codeforces.com/blog/entry/62393

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

// Usage:
unordered_map<long long, int, custom_hash> safe_map;
gp_hash_table<long long, int, custom_hash> safe_hash_table;