Skip to content

Instantly share code, notes, and snippets.

@MiSawa
MiSawa / dinic_worst.cc
Created Apr 24, 2021
Dinic worst case behavior
View dinic_worst.cc
#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#include <vector>
#include <vector>
namespace atcoder {
@MiSawa
MiSawa / gen.cpp
Last active Jan 15, 2021
Exponential instance for a wrong implementation of Dinic
View gen.cpp
#include <iostream>
#include <vector>
#include <tuple>
#include <array>
// s u - u - u - u
// | > a < X X X > c - t
// b v - v - v - v
@MiSawa
MiSawa / ModInt.cc
Last active Apr 22, 2019
俺の考えた最強の ModInt. http://tokoharuland.hateblo.jp/entry/2019/04/22/004513 に感化されて書いたやつ.
View ModInt.cc
#include <iostream>
#include <type_traits>
// param > 0 => use param as the modulo
// param <= 0 => you can set the modulo with ModInt<param>::set_modulo(...) in runtime.
// Of course, those runtime modulo will be distinguished if the param was different.
template<int param>
class ModInt{//{{{
using Z = int;
using N = unsigned int;
@MiSawa
MiSawa / ICPCAugRelabel.cc
Last active Nov 29, 2021
AugmentRelabel
View ICPCAugRelabel.cc
using ll = long long;
// https://gist.github.com/MiSawa/2818cf0bfdb27d42c429f2adb7ee9bc0
// バグってても責任とりません >_<
// 下に行くほど最適化が減る代わりに記述が楽になります
struct ICPCAugRelabel {//{{{
using Flow = int64_t;
constexpr static Flow INF = numeric_limits<Flow>::max();
struct E{
size_t t, rev;
View scanner.cc
#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define rall(x) (x).rbegin(),(x).rend()
#define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define repsz(i,v) rep(i,(v).size())
#define aur auto&
#define bit(n) (1LL<<(n))
#define eb emplace_back
#define mt make_tuple
View keyword.cc
#include <bits/stdc++.h>
using namespace std;
namespace KeyWordArguments{//{{{
template<typename T>
class KeyWord {//{{{
using type = T;
KeyWord(const size_t &id, const T &val) : id(id), val(val) {}
static inline size_t get_id(){ static size_t count = 0; return count++; }
public:
@MiSawa
MiSawa / main.cc
Created Jun 14, 2015
template for dcj
View main.cc
#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define rall(x) (x).rbegin(),(x).rend()
#define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define repsz(i,v) rep(i,(v).size())
#define aur auto&
#define bit(n) (1LL<<(n))
#define eb emplace_back
#define mt make_tuple
View bb.cc
// https://codeiq.jp/ace/kawazoe/q1339
#include <iostream>
#include <vector>
long long k_bonacci(const int &k, const int &n){
std::vector<long long> v(k, 0);
long long res = v.back() = 1;
for(int i = 0; i < n; ++i) std::swap(v[i%k] = res * 2 - v[i%k], res);
return res;
}
int main(){
View memoize.cc
#include <bits/stdc++.h>
using namespace std;
template<typename Res, typename ...Args> struct _memoized{//{{{
function<Res(Args...)> f;
map<tuple<Args...>, Res> memo;
_memoized(function<Res(Args...)> &f) : f(f){}
Res operator()(Args ...args){
const auto &key = make_tuple(args...);
View adj.cc
#include <bits/stdc++.h>
using namespace std;
typedef complex<int> P;
struct adjacent{
P p;
adjacent(const P &p) : p(p){}
template<typename ...Args> adjacent(const Args &...args) : p(args...){}
struct Iter : public forward_iterator_tag {