去掉了许多用不到的内容,包括数据结构。
进一步优化了输入输出。
抄袭 acwing_gza 加入了图板块。
共 $387$ 行。
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
namespace helper
{
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef unsigned long long ULL;
typedef std::pair<int, int> PII;
typedef std::pair<double, double> PDD;
typedef std::vector<int> VI;
typedef std::vector<LL> VLL;
typedef std::vector<ULL> VULL;
typedef std::vector<PII> VPII;
typedef std::vector<PDD> VPDD;
typedef std::vector<VI> VVI;
#define f(i, a, b, c) for (i = a; i < b && i - c > b || a > b && i - c < b; i ++ )
#define r(it, s, e) for (it = s; it != e; it ++ )
#define w(n) while (n -- )
#define F first
#define S second
#define EP emplace
#define EB emplace_back
#define mcp(a, b) memcpy((a), (b), sizeof(a));
#define mcp2(a, b) memcpy((a), (b), sizeof(b));
#define f_inf(a) memset((a), 0x3f, sizeof(a));
#define f_h(a) memset((a), -1, sizeof(a));
#define RT return
#define UM unordered_map
#define US unordered_set
#define BS bitset
#define PQ priority_queue
#define GT greater
#define MC memcpy
#define MS memset
#define LH(T) PQ<T, V<T>, GT<T>>
}
namespace IO
{
const int MAX = 1 << 24;
static char buf[MAX], *p1 = buf, *p2 = buf;
static char outbuf[MAX], *out = outbuf;
#define input() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAX, stdin), p1 == p2) ? EOF : *p1 ++ )
#define output(x) *out ++ = x
#define flush() fwrite(outbuf, 1, out - outbuf, stdout)
inline bool read(char *t)
{
memset(t, 0, sizeof t);
char *pd = t, c = input();
while (isspace(c)) c = input();
while (c ^ EOF && !isspace(c)) *pd ++ = c, c = input();
return c ^ EOF;
}
template <class T>
inline bool read(T &t)
{
t = 0;
char c = input(), f = 1;
while (isspace(c)) c = input();
if (c == '-') f = -1, c = input();
while (c ^ EOF && isdigit(c)) t = (t << 3) + (t << 1) + (c ^ 48), c = input();
t *= f;
return c ^ EOF;
}
template <class T>
inline bool read(T *t, int len)
{
static int i = 0;
for (; i < len; i ++ )
if (!read(t[i]))
break;
return i;
}
template <class T, class ...Args>
inline bool read(T &t, Args &...args)
{
return read(t) ? 1 : read(args...);
}
inline void print(char *s, int len)
{
for (int i = 0; i < len; i ++ ) output(s[i]);
}
template <class T>
inline void write(T x)
{
if (x < 0)
{
output('-');
x = -x;
}
if (!x) return output('0'), void();
static char t[40], p = 0;
while (x) t[ ++ p] = x % 10 ^ 48, x /= 10;
while (p) output(t[p -- ]);
}
template <class T>
inline void write(T *t, int len, char split=' ')
{
for (int i = 0; i < len; i ++ )
{
write(t[i]);
if (i ^ len - 1) output(split);
}
}
}
namespace math
{
template <class T>
T qpow(T a, T b, T p)
{
T res = 1 % p;
while (b)
{
if (b & 1) res = (__uint128_t)res * a % p;
a = (__uint128_t)a * a % p, b >>= 1;
}
return res;
}
template <class T>
T smul(T a, T b, T p)
{
T res = 0;
while (b)
{
if (b & 1) res = ((__uint128_t)res + a) % p;
a = ((__uint128_t)a << 1) % p, b >>= 1;
}
return res;
}
template <class T>
T gcd(T a, T b)
{
return b ? gcd(b, a % b) : a;
}
template <class T>
T exgcd(T a, T b, T &x, T &y)
{
if (!b)
{
x = 1, y = 0;
return a;
}
T d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
std::vector<int> add(std::vector<int> &A, std::vector<int> &B)
{
if (A.size() < B.size()) return add(B, A);
std::vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(t);
return C;
}
std::vector<int> sub(std::vector<int> &A, std::vector<int> &B)
{
std::vector<int> C;
for (int i = 0, t = 0; i < A.size(); i ++ )
{
t = A[i] - t;
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
std::vector<int> mul(std::vector<int> &A, int b)
{
std::vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
std::vector<int> div(std::vector<int> &A, int b, int &r)
{
std::vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i -- )
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
template <class T>
bool is_prime(T x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
std::vector<int> get_divisors(int x)
{
std::vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}
template <class T>
T phi(T x)
{
T res = x;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
int C(int a, int b, int p)
{
if (a < b) return 0;
long long x = 1, y = 1;
for (int i = a, j = 1; j <= b; i -- , j ++ )
{
x = (long long)x * i % p;
y = (long long)y * j % p;
}
return x * (long long)qpow(y, (long long)p - 2, (long long)p) % p;
}
int lucas(long long a, long long b, int p)
{
if (a < p && b < p) return C(a, b, p);
return (long long)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
}
namespace graph
{
const int MAX_N = 1 << 19, MAX_M = 1 << 19;
int h[MAX_N], e[MAX_M], w[MAX_M], ne[MAX_M], idx;
int dist[MAX_N];
bool st[MAX_N];
memset(h, -1, sizeof h);
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra(int start = 1)
{
memset(dist, 0x3f, sizeof dist);
memset(st, false, sizeof st);
dist[start] = 0;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> q;
q.push({0, start});
while (!q.empty())
{
int t = q.top().second;
q.pop();
if (st[t]) continue;
st[t] = true;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
q.push({dist[j], j});
}
}
}
}
void spfa(int start = 1)
{
memset(dist, 0x3f, sizeof dist);
memset(st, false, sizeof st);
std::queue<int> q;
dist[start] = 0, st[start] = true;
q.push(start);
while (!q.empty())
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
}
}
using namespace helper;
using namespace IO;
using namespace std;
int main()
{
// 程序
flush();
RT 0;
}
你这……是干蛤的??(我是小白)
不错hh
可恶