NULL
inline void read (int &now) { register char word = getchar (); int temp = 0; for (now = 0; !isdigit (word); word = getchar ()) if (word == '-') temp = 1; for (; isdigit (word); now = now * 10 + word - '0', word = getchar ()); if (temp) now = -now; }
int BUF = 1000010; char Buf[1000010], *buf = Buf; void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); }
#include <cstdio> #include <iostream> #define INF 1e9 inline void read (int &now) { register char c = getchar (); int temp = 0; for (now = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); now = now * 10 + c - '0', c = getchar ()); } using namespace std; #define Max 2020 int N, M, V, E; double map[Max][Max]; int room[Max], other[Max]; double k[Max]; double dp[Max][Max][2]; int Main () { freopen ("classroom.in", "r", stdin); freopen ("classroom.ans", "w", stdout); read (N), read (M), read (V), read (E); register int i, j; for (i = 1; i <= N; ++ i) read (room[i]); for (i = 1; i <= N; ++ i) read (other[i]); for (i = 1; i <= N; ++ i) scanf ("%lf", &k[i]); int x, y, z; for (i = 1; i <= V; ++ i) for (j = 1; j <= V; ++ j) if (i == j) map[i][i] = 0; else map[i][j] = INF; for (i = 1; i <= E; ++ i) { read (x), read (y), read (z); if (x == y) continue; map[x][y] = min (map[x][y], (double)z); map[y][x] = map[x][y]; } int pos; for (pos = 1; pos <= V; ++ pos) for (i = 1; i <= V; ++ i) for (j = 1; j <= V; ++ j) map[i][j] = min (map[i][j], map[i][pos] + map[pos][j]); int L; double res; for (i = 0; i <= N; ++ i) for (j = 0; j <= M; ++ j) dp[i][j][0] = dp[i][j][1] = INF; dp[1][0][0] = 0, dp[1][1][1] = 0; for (i = 2; i <= N; ++ i) { dp[i][0][0] = dp[i - 1][0][0] + map[room[i - 1]][room[i]]; for (j = 1, L = min (M, i); j <= L; ++ j) { dp[i][j][0] = min (dp[i - 1][j][0] + map[room[i - 1]][room[i]], dp[i - 1][j][1] + map[room[i - 1]][room[i]] * (1.0 - k[i - 1]) + map[other[i - 1]][room[i]] * k[i - 1]); dp[i][j][1] = dp[i - 1][j - 1][0] + map[room[i - 1]][room[i]] * (1.0 - k[i]) + map[room[i - 1]][other[i]] * k[i]; res = dp[i - 1][j - 1][1] + map[room[i - 1]][room[i]] * (1.0 - k[i - 1]) * (1.0 - k[i]); res += map[other[i - 1]][room[i]] * k[i - 1] * (1.0 - k[i]); res += map[room[i - 1]][other[i]] * (1.0 - k[i - 1]) * k[i]; res += map[other[i - 1]][other[i]] * k[i - 1] * k[i]; dp[i][j][1] = min (dp[i][j][1], res); } } double Answer = INF; for (i = 0; i <= M; ++ i) Answer = min (Answer, min (dp[N][i][0], dp[N][i][1])); printf ("%.2lf", Answer); fclose (stdin); fclose (stdout); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <iostream> #include <cstdio> const int BUF = 10000022; char Buf[BUF], *buf = Buf; void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } #define Max 2010 int C[Max + 2][Max + 2]; int sum[Max + 2][Max + 2]; inline int min (int a, int b) { return a < b ? a : b; } int data[Max + 2]; int Main () { freopen ("problem.in", "r", stdin); freopen ("problem.ans", "w", stdout); fread (buf, 1, BUF, stdin); int N, M, K; int T; read (T), read (K); C[0][0] = 1; register int i, j; int S = 0; for (i = 1; i <= Max; ++ i) { C[i][0] = 1; for (j = 1; j <= i; j ++) { C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % K; if (C[i][j] == 0) ++ data[i]; if (i == j) sum[i][j] = sum[i - 1][j - 1] + data[i]; else sum[i][j] = sum[i - 1][j] + data[i]; } } int x, y; for (i = 1; i <= T; ++ i) { read (x), read (y); printf ("%d ", sum[x][min (y, x)]); } return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> #include <algorithm> #include <queue> const int BUF = 10102030; char Buf[BUF], *buf = Buf; #define Inline __attri bute__( ( optimize ( "-O2" ) ) ) Inline void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } std :: priority_queue <int> Heap; int Tag; Inline void write (int x) { if (x > 9) write (x / 10); putchar (x % 10 + '0'); } Inline int Main () { freopen ("earthworm.in", "r", stdin); freopen ("earthworm.ans", "w", stdout); fread (buf, 1, BUF, stdin); int N, M, Q, U, V, T; read (N), read (M), read (Q), read (U), read (V), read (T); register int i; int x; double k = (double)U / V; for (i = 1; i <= N; ++ i) { read (x); Heap.push (x); } register int pos; for (i = 1; i <= M; ++ i) { pos = Heap.top () + Tag, Heap.pop (); if (i % T == 0) write (pos), putchar (' '); x = (int)(k * pos), Heap.push (x - Tag - Q), Heap.push (pos - x - Tag - Q); Tag += Q; } putchar (' '); for (i = 1; i <= N + M; ++ i) { if (i % T == 0) write (Heap.top () + Tag), putchar (' '); Heap.pop (); } return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include<cstdio> #include<iostream> #include<algorithm> #define Max 100010 const int BUF = 10000010; char Buf[BUF], *buf = Buf; void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } int data[Max]; struct Queue { protected : int H, T, c[Max * 80]; public : Queue () { H = 1; T = 0; } inline void push (int key) { c[++ T] = key;} inline void pop () { ++ H; } inline int front () { return c[H]; } inline bool empty () { return H > T; } }; Queue queue[3]; int Get_Max () { int now; for (int i = 0; i <= 2; ++ i) { if (queue[i].empty ()) continue; if (i != 0 && !queue[0].empty () && queue[0].front () > queue[i].front ()) continue; if (i != 1 && !queue[1].empty () && queue[1].front () > queue[i].front ()) continue; if (i != 2 && !queue[2].empty () && queue[2].front () > queue[i].front ()) continue; now = queue[i].front (), queue[i].pop (); return now; } } int Main () { freopen ("earthworm.in", "r", stdin); freopen ("earthworm.ans", "w", stdout); fread (buf, 1, BUF, stdin); int N, M, Q, U, V, T; register int i, pos, Tag = 0; read (N), read (M), read (Q), read (U), read (V), read (T); for (i = 1; i <= N; ++ i) read (data[i]); std :: sort (data + 1, data + N + 1); for (i = N; i >= 1; -- i) queue[0].push (data[i]); for (i = 1; i <= M; ++ i) { pos = Get_Max (); if (i % T == 0) printf ("%d ", pos + Tag); queue[1].push ((long long)(pos + Tag) * U / V - Tag - Q); queue[2].push ((pos + Tag) - (long long)(pos + Tag) * U / V - Tag - Q); Tag += Q; } putchar (' '); for (i = 1; !queue[0].empty () || !queue[1].empty () || !queue[2].empty(); ++ i) { pos = Get_Max (); if (i % T == 0) printf ("%d ", pos + Tag); } return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define Max 25 #define EPS 1e-8 inline void read (int &now) { register char c = getchar (); for (now = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); now = now * 10 + c - '0', c = getchar ()); } int T, N, M, Answer; struct Point { double x, y; }; struct Line { double a, b, x, y; }; Point p[Max]; Line b[Max]; int use[Max]; bool visit[Max]; inline double Cal (int pos, int z) { return fabs (b[pos].a * p[z].x * p[z].x + b[pos].b * p[z].x - p[z].y); } void Dfs (int n, int res) { if (n > N) { if (res < Answer) Answer = res; return; } if (res >= Answer) return; for (int i = 1; i <= res; ++ i) if (use[i] <= 1) { double X1 = b[i].x, Y1 = b[i].y, X2 = p[n].x, Y2 = p[n].y; double d = X1 / X2; if (fabs (X1 * X2 - X1 * X1) <= EPS) continue; b[i].a = (Y2 * d - Y1) / (X1 * X2 - X1 * X1); b[i].b = (Y1 - b[i].a * X1 * X1) / X1; if (b[i].a >= -EPS) continue; ++ use[i], Dfs (n + 1,res), -- use[i]; } else if (Cal (i, n) <= EPS) Dfs (n + 1, res); b[res + 1].x = p[n].x, b[res + 1].y = p[n].y; use[res + 1] = 1, Dfs (n + 1, res + 1), use[res + 1] = 0; } int Main () { freopen ("angrybirds.in", "r", stdin); freopen ("angrybirds.ans", "w", stdout); read (T); for (; T; -- T) { read (N), read (M); Answer = 25; memset (p, 0, sizeof p); memset (b, 0, sizeof b); memset (use, 0, sizeof use); for (int i = 1; i <= N; ++ i) scanf ("%lf%lf", &p[i].x, &p[i].y); Dfs (1, 0); printf ("%d ", Answer); } return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #define Max 50 int map[Max][Max]; int Main () { freopen ("magic.in", "r", stdin); freopen ("magic.ans", "w", stdout); int N, j; scanf ("%d", &N); register int i, x = 1, y = ((N >> 1) + 1); int L = N * N; map[x][y] = 1; for (i = 2; i <= L; ++ i) { if (x == 1 && y != N) x = N, ++ y; else if (y == N && x != 1) -- x, y = 1; else if (x == 1 && y == N) ++ x; else if (x != 1 && y != N) { if (map[x - 1][y + 1] == 0) -- x, ++ y; else ++ x; } map[x][y] = i; } for (i = 1; i <= N; ++ i) { for (j = 1; j <= N; ++ j) printf ("%d ", map[i][j]); putchar (' '); } return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> #include <stack> const int BUF = 10001023; char Buf[BUF], *buf = Buf; inline void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } #define Max 300000 int N, Answer = 1e9; inline int min (int a, int b) { return a < b ? a : b; } class Tarjan_Type { private : int to[Max], _next[Max], C, list[Max]; int scc_number[Max], Scc_C, dfn[Max], low[Max], D_C; std :: stack <int> Stack; public : Tarjan_Type () { C = 0, Scc_C = 0, D_C = 0; } inline void In (int u, int v) { to[++ C] = v, _next[C] = list[u], list[u] = C; } void Do_Tarjan () { for (int i = 1; i <= N; ++ i) if (!dfn[i]) Dfs (i); } void Dfs (int now) { dfn[now] = low[now] = ++ D_C, Stack.push (now); for (int i = list[now]; i; i = _next[i]) { if (!dfn[to[i]]) { Dfs (to[i]); low[now] = min (low[to[i]], low[now]); } else if (!scc_number[to[i]]) low[now] = min (dfn[to[i]], low[now]); } if (dfn[now] == low[now]) { ++ Scc_C; int pos = now + 1, res = 0; for (; pos != now && !Stack.empty (); Stack.pop ()) pos = Stack.top (), scc_number[pos] = Scc_C, ++ res; if (res != 1) Answer = min (Answer, res); } } }; Tarjan_Type Tar; int Main () { freopen ("message.in", "r", stdin); freopen ("message.ans", "w", stdout); fread (buf, 1, BUF, stdin); read (N); int x; for (int i = 1; i <= N; ++ i) read (x), Tar.In (i, x); Tar.Do_Tarjan (); printf ("%d", Answer); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <iostream> #include <cstdio> #include <cstring> #define INF 1e7 const int BUF = 1000100; char Buf[BUF], *buf = Buf; inline void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } #define Max 30 int T, N, Answer ; int card[Max], count[Max]; inline int min (int a, int b) { return a < b ? a : b; } void Dfs (int now) { if (now > Answer) return; int res = 0; register int i, j; for (i = 0; i < 30; i ++) count[i] = 0; for (i = 0; i <= 14; i++) count[card[i]]++; for (; count[4]; ) { -- count[4], ++ res; if (count[2] >= 2) count[2] -= 2; else if (count[1] >= 2) count[1] -= 2; } for (; count[3]; ) { -- count[3], ++ res; if (count[2]) -- count[2]; else if (count[1]) -- count[1]; } if (card[0] && card[1] && count[1] >= 2) -- res; res += count[1] + count[2], Answer = min (res + now, Answer); for (i = 3, j; i <= 14; ++i) { for (j = i; card[j] && j <= 14; ++j) { -- card[j]; if (j - i + 1 >= 5) Dfs (now + 1); } for (; j > i; ) ++ card [--j]; } for (i = 3, j; i <= 15; ++i) { for (j = i; card[j] >= 2 && j <= 14; ++j) { card[j] -= 2; if (j - i + 1 >= 3) Dfs (now + 1); } for (; j > i; ) card [--j] += 2; } for (i = 3, j; i <= 15; ++i) { for (j = i; card[j] >= 3 && j <= 14; ++j) { card[j] -= 3; if (j - i + 1 >= 2) Dfs (now + 1); } for (; j > i; ) card [--j] += 3; } } int Main () { freopen ("landlords.in", "r", stdin); freopen ("landlords.ans", "w", stdout); fread (buf, 1, BUF, stdin); read (T), read (N); int x, y; register int i; for (; T; -- T) { memset (card, 0, sizeof (card)); Answer = INF; for (i = 1; i <= N; ++ i) { read (x), read (y); if (x == 0) ++ card [y - 1]; else if (x == 1) ++ card [14]; else ++ card[x]; } Dfs (0); printf ("%d ", Answer); } return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> const int BUF = 10000012; char Buf[BUF], *buf = Buf; inline void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } #define Max 60000 int N, L, M; int key[Max]; bool Check (int Thb) { int res = 0, C = 0, last = 0; for (int i = 1; i <= N; ++ i) { if (key[i] - last < Thb) ++ C; else last = key[i]; if (C > M) return false; } return true; } int Main () { freopen ("stone.in", "r", stdin); freopen ("stone.ans", "w", stdout); fread (buf, 1, BUF, stdin); read (L), read (N), read (M); int l = 0, r = L, Mid; for (int i = 1; i <= N; ++ i) read (key[i]); int Answer; for (; l <= r; ) { Mid = l + r >> 1; if (Check (Mid)) { Answer = Mid; l = Mid + 1; } else r = Mid - 1; } printf ("%d", Answer); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> #define Max 1030 void read (int &now) { register char c = getchar (); for (now = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); now = now * 10 + c - '0', c = getchar ()); } #define Mod 1000000007 int N, M, K; char A[Max], B[Max]; int dp[Max][Max][Max / 10 * 2]; int pos = 1, next; int data[Max][Max][Max / 10 * 2]; int Main () { freopen ("substring.in", "r", stdin); freopen ("substring.ans", "w", stdout); dp[0][0][0] = 1; read (N), read (M), read (K); scanf ("%s%s", A + 1, B + 1); register int i, j, k; int Answer; for (i = 1; i <= N; ++ i) { dp[pos][0][0] = 1; for (j = 1; j <= M; ++ j) for (k = 1; k <= K; ++ k) { if (A[i] != B[j]) data[pos][j][k] = 0; else data[pos][j][k] = (data[next][j - 1][k] + dp[next][j - 1][k - 1]) % Mod; dp[pos][j][k] = (dp[next][j][k] + data[pos][j][k]) % Mod; } k = pos, pos = next, next = k; Answer = next; } printf ("%d", dp[Answer][M][K]); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> #include <cstdlib> #define Inline __attri bute__( ( optimize ( "-O2" ) ) ) const int BUF = 234234234; char Buf[BUF], *buf = Buf; #define INF 1e9 Inline void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } #define Max 300050 int N, M; int t_n[Max]; Inline void swap (int &x, int &y) { int now = x; x = y, y = now; } struct Bit_Tree { protected : int sum[Max]; int N; public : Inline void Prepare (const int &x) { this->N = x; for (register int i = 1; i <= N; ++ i) sum[i] = 0; } Inline int Ask (int l, int r) { int res = 0; for (-- l; l; l -= l & (-l)) res -= sum[l]; for (; r; r -= r & (-r)) res += sum[r]; return res; } Inline void Change (int pos, int to) { for (; pos <= N; pos += pos & (-pos)) sum[pos] += to; } }; Bit_Tree Bit; inline int min (int a, int b) { return a < b ? a : b; } inline int max (int a, int b) { return a > b ? a : b; } class Tree_Chain_Get { private : int to[Max << 1], _next[Max << 1], dis[Max << 1], C, list[Max]; int deep[Max], size[Max], father[Max], chain[Max], son[Max]; int value[Max], key[Max], Count; public : Inline void In (const int &M) { int x, y, z; for (register int i = 1; i <= M; ++ i) { read (x), read (y), read (z); to[++ C] = y, _next[C] = list[x], list[x] = C, value[C] = z; to[++ C] = x, _next[C] = list[y], list[y] = C, value[C] = z; } Bit.Prepare (M + 1); Dfs_1 (1, 0), Count = 0, Dfs_2 (1, 1); } void Dfs_1 (int now, int Father) { father[now] = Father, size[now] = 1, deep[now] = deep[Father] + 1; for (int i = list[now]; i; i = _next[i]) if (to[i] != Father) { Dfs_1 (to[i], now); size[now] += size[to[i]]; if (size[son[now]] < size[to[i]]) son[now] = to[i]; } } void Dfs_2 (int now, int point) { chain[now] = point; for (int i = list[now]; i; i = _next[i]) if (to[i] == father[now]) { key[now] = value[i]; break; } t_n[now] = ++ Count; Bit.Change (Count, key[now]); if (son[now]) Dfs_2 (son[now], point); else return ; for (int i = list[now]; i; i = _next[i]) if (to[i] != son[now] && to[i] != father[now]) Dfs_2 (to[i], to[i]); } Inline int Q (int x, int y) { int res = 0; for (; chain[x] != chain[y]; ) { if (deep[chain[x]] < deep[chain[y]]) swap (x, y); res += Bit.Ask (t_n[chain[x]], t_n[x]); x = father[chain[x]]; } if (deep[x] > deep[y]) swap (x, y); if (x != y) res += Bit.Ask (t_n[x] + 1, t_n[y]); return res; } }; Tree_Chain_Get T; int q_x[Max], q_y[Max]; Inline int Main () { freopen ("transport.in", "r", stdin); freopen ("transport.ans", "w", stdout); fread (buf, 1, BUF, stdin); read (N), read (M); T.In (N - 1); int x, y; register int i, j; for (i = 1; i <= M; ++ i) read (q_x[i]), read (q_y[i]); int Answer = INF, now, res, pos; for (i = 2; i <= N; ++ i) { pos = t_n[i]; now = Bit.Ask (pos, pos); res = -1; Bit.Change (pos, -now); for (j = 1; j <= M; ++ j) res = max (res, T.Q (q_x[j], q_y[j])); Answer = min (Answer, res); Bit.Change (pos, now); } printf ("%d", Answer); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> #include <cstring> const int BUF = 12312312; char Buf[BUF], *buf = Buf; inline void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } #define Max 300 int c[Max], d[Max]; int map[5][5]; int Main () { freopen ("rps.in", "r", stdin); freopen ("rps.ans", "w", stdout); fread (buf, 1, BUF, stdin); int N, A, B; read (N), read (A), read (B); register int i, j, k; for (i = 1; i <= A; ++ i) read (c[i]); for (i = 1; i <= B; ++ i) read (d[i]); memset (map, - 1, sizeof map); for (i = 0; i < 5; ++ i) map[i][i] = 0; map[0][1] = 2, map[0][4] = 2, map[1][2] = 2, map[1][4] = 2; map[0][2] = 1, map[0][3] = 1, map[2][3] = 2; map[1][3] = 1, map[2][4] = 1, map[3][4] = 1; int Z = 0, X = 0; for (i = 1, j = 1, k = 1; i <= N; ++ i, ++ j, ++ k) { if (j == A + 1) j = 1; if (k == B + 1) k = 1; if (map[c[j]][d[k]] == -1) { if (map[d[k]][c[j]] == 1) ++ X; else if (map[d[k]][c[j]] == 2) ++ Z; continue; } if (map[c[j]][d[k]] == 1) ++ Z; else if (map[c[j]][d[k]] == 2) ++ X; } printf ("%d %d", Z, X); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> const int BUF = 12312312; char Buf[BUF], *buf = Buf; void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } #define Max 200200 struct E { E *n; int to; }; E poor[Max << 1], *Tail = poor, *list[Max]; int key[Max]; #define Mod 10007 inline void In (int u, int v) { ++ Tail, Tail->to = v, Tail->n = list[u], list[u] = Tail; ++ Tail, Tail->to = u, Tail->n = list[v], list[v] = Tail; } int N, father[Max]; int T, Answer = -1; inline int max (int a, int b) { return a > b ? a : b; } void Dfs (int now, int Father) { father[now] = Father; int Grand = father[Father], res; if ((res = key[now] * key[Grand]) != 0) { Answer = max (Answer, res); T = (T + ((res % Mod) << 1)); } for (E *e = list[Father]; e; e = e->n) if (e->to != now && e->to != Grand) { res = key[e->to] * key[now]; Answer = max (Answer, res); T = (T + res) % Mod; } for (E *e = list[now]; e; e = e->n) if (e->to != Father) Dfs (e->to, now); } int Main () { freopen ("link.in", "r", stdin); freopen ("link.ans", "w", stdout); fread (buf, 1, BUF, stdin); read (N); int x, y; for (int i = 1; i < N; ++ i) { read (x), read (y); In (x, y); } for (int i = 1; i <= N; ++ i) read (key[i]); Dfs (1, 0); printf ("%d %d", Answer, T); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> #include <algorithm> const int BUF = 12312312; char Buf[BUF], *buf = Buf; #define INF 1e8 inline void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } #define Max 100030 int up[Max], down[Max], N, M, K; int u[Max], d[Max], Answer = INF, Z; inline int min (int a, int b) { return a < b ? a : b; } bool flag = false; void Dfs (int x, int h, int c) { if (c > Answer) return ; if (x > Z) Z = x; if (x == N) { flag = true; Answer = min (Answer, c); return ; } if (u[x + 1] == 0) for (int i = 1; h + i * up[x] > d[x + 1]; ++ i) { if (h + i * up[x] >= M) { Dfs (x + 1, M, c + i); break; } else Dfs (x + 1, h + i * up[x], c + i); } else for (int i = 1; (h + i * up[x]) > d[x + 1] && (h + i * up[x] < u[x + 1]); ++ i) Dfs (x + 1, h + i * up[x], c + i); if (h - down[x] > d[x + 1] && h - down[x] < (u[x + 1] == 0 ? INF : u[x + 1])) Dfs (x + 1, h - down[x], c); } int Main () { freopen ("bird.in", "r", stdin); freopen ("bird.ans", "w", stdout); fread (buf, 1, BUF, stdin); register int i; read (N), read (M), read (K); for (i = 0; i < N; ++ i) read (up[i]), read (down[i]); int x; for (i = 1; i <= K; ++ i) read (x), read (d[x]), read (u[x]); for (i = 1; i <= M; ++ i) Dfs (0, i, 0); if (flag) printf ("1 %d", Answer); else { int res = 0; for (i = 1; i <= Z; ++ i) if (u[i]) ++ res; printf ("0 %d", res); } return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> const int BUF = 12312313; char Buf[BUF], *buf = Buf; inline void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } #define Max 130 int map[Max][Max]; const int N = Max - 1; inline int max (int a, int b) { return a > b ? a : b; } inline int min (int a, int b) { return a < b ? a : b; } int Main () { freopen ("wireless.in", "r", stdin); freopen ("wireless.ans", "w", stdout); fread (buf, 1, BUF, stdin); int D, K; read (D), read (K); register int i, j; int x, y, z; for (i = 1; i <= K; ++ i) { read (x), read (y), read (z); map[x][y] = z; } int Answer = -1, C = 0, res; for (x = 0; x < N; ++ x) for (y = 0; y < N; ++ y) { res = 0; for (i = -D; i <= D; ++ i) for (j = -D; j <= D; ++ j) res += map[min (N - 1, max (0, x - i))][min (N - 1, max (0, y - j))]; if (res == Answer) ++ C; if (res > Answer) Answer = res, C = 1; } printf ("%d %d", C, Answer); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> #include <queue> #include <cstring> #include <cstdlib> #define Max 220200 const int BUF = 123123123; char Buf[BUF], *buf = Buf; inline void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } struct E { E *n; int to; }; E *list[Max], poor[Max << 1], *Tail = poor; bool visit[Max]; void F_Bfs (const int &S, const int &T) { std :: queue <int> Queue; int now; visit[S] = true; for (Queue.push (S); !Queue.empty (); Queue.pop ()) { now = Queue.front (); for (E *e = list[now]; e; e = e->n) if (!visit[e->to]) { visit[e->to] = true; Queue.push (e->to); } } } int dis[Max]; void Z_Bfs (const int &S, const int &T) { memset (dis, -1, sizeof dis); E *e; std :: queue <int> Queue; int now; dis[S] = 0; for (Queue.push (S); !Queue.empty (); Queue.pop ()) { now = Queue.front (); for (e = list[now]; e; e = e->n) if (!visit[e->to]) goto Continue; for (e = list[now]; e; e = e->n) if (dis[e->to] == -1) { dis[e->to] = dis[now] + 1; Queue.push (e->to); if (e->to == T) { printf ("%d", dis[T]); exit (0); } } Continue : continue; } } int da_x[Max], da_y[Max]; int Main () { freopen ("road.in", "r", stdin); freopen ("road.ans", "w", stdout); fread (buf, 1, BUF, stdin); int N, M, x, y, z, S, T; read (N), read (M); register int i; for (i = 1; i <= M; ++ i) { read (da_x[i]), read (da_y[i]); ++ Tail, Tail->to = da_x[i], Tail->n = list[da_y[i]], list[da_y[i]] = Tail; } read (S), read (T); F_Bfs (T, S); for (i = 1; i <= M; ++ i) list[i] = NULL; for (i = 1, Tail = poor; i <= M; ++ i) ++ Tail, Tail->to = da_y[i], Tail->n = list[da_x[i]], list[da_x[i]] = Tail; Z_Bfs (S, T); printf ("-1"); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> const int BUF = 12312312; char Buf[BUF], *buf = Buf; void read (int &now) { int temp = 0; for (now = 0; !isdigit (*buf); ++ buf) if (*buf == '-') temp = 1; for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); if (temp) now = -now; } #define Max 100 int a[Max]; long long F_P (int x, int p) { if (p == 0) return 1; long long res = 1; for (; p; p >>= 1) { if (p & 1) res *= x; x *= x; } return res; } int Main () { freopen ("equation.in", "r", stdin); freopen ("equation.ans", "w", stdout); fread (buf, 1, BUF, stdin); int N, M; register int i; read (N), read (M); for (i = 0; i <= N; ++ i) read (a[i]); register int j; int C = 0; long long res; static int Answer[Max]; for (i = 1; i <= M; ++ i) { res = 0; for (j = 0; j <= N; ++ j) res += a[j] * F_P (i, j); if (!res) Answer[++ C] = i; } printf ("%d ", C); for (i = 1; i <= C; ++ i) printf ("%d ", Answer[i]); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> const int BUF = 12312312; char Buf[BUF], *buf = Buf; inline void read (long long &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } long long Q_P (long long x, long long p, long long Mod) { long long res = 1; for (; p; p >>= 1) { if (p & 1) res = (res * x) % Mod; x = (x * x) % Mod; } return res; } void write (long long now) { if (now > 9) write (now / 10); putchar (now % 10 + '0'); } int Main () { freopen ("circle.in", "r", stdin); freopen ("circle.ans", "w", stdout); fread (buf, 1, BUF, stdin); long long N, M, K, X; read (N), read (M), read (K), read (X); write ((X + M * Q_P (10, K, N)) % N); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> #include <algorithm> const int BUF = 123123123; char Buf[BUF], *buf = Buf; inline void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } #define INF 1e9 #define Max 30100 struct E { E *n; int to, key; }; E *list[Max], poor[Max], *Tail = poor; struct Edge { int from, to, key; bool operator < (const Edge &now) const { return this->key > now.key; } }; Edge data[Max * 5]; struct Unio_Find { protected : int data[Max]; public : void Prepare (const int &N) { for (register int i = 1; i <= N; ++ i) data[i] = i; } int Find (int x) { return data[x] == x ? x : data[x] = Find (data[x]); } inline void Unio (int x, int y) { data[x] = y; } }; Unio_Find Ufs; inline int min (int a, int b) { return a < b ? a : b; } int N, M; struct S_D { S_D *Left, *Right; int key, Mid; inline void Up () { this->key = min (this->Left->key, this->Right->key); } }; int tree_key[Max], in[Max]; inline void swap (int &a, int &b) { int now = a; a = b, b = now; } class Segment_Tree { private : S_D _poor[Max], *Tail, *Root; inline S_D *New (int x, int y) { ++ this->Tail, this->Tail->Mid = x + y >> 1, this->Tail->key = 0; this->Tail->Left = this->Tail->Right = NULL; return this->Tail; } void Build (S_D *&now, int l, int r) { now = New (l, r); if (l == r) { now->key = tree_key[l]; return ; } Build (now->Left, l, now->Mid); Build (now->Right, now->Mid + 1, r); now->Up (); } int Query (S_D *&now, int L, int R, int l, int r) { if (l <= L && R <= r) return now->key; int res = INF; if (l <= now->Mid) res = Query (now->Left, L, now->Mid, l, r); if (r > now->Mid) res = min (res, Query (now->Right, now->Mid + 1, R, l, r)); return res; } public : Segment_Tree () { this->Tail = _poor;} void Build (int l, int r) { return Build (Root, l, r); } int Query (int l, int r) { return Query (Root, 1, N, l, r); } }; Segment_Tree Seg; class Tree_Chain_Get_Type { private : int deep[Max], size[Max], father[Max], chain[Max], son[Max]; int C; void Dfs_1 (int now, int Father) { size[now] = 1, father[now] = Father, deep[now] = deep[Father] + 1; for (E *e = list[now]; e; e = e->n) if (e->to != Father) { Dfs_1 (e->to, now); size[now] += size[e->to]; if (size[son[now]] < size[e->to]) son[now] = e->to; } } void Dfs_2 (int now, int point) { chain[now] = point; in[now] = ++ C; E *e; for (e = list[now]; e; e = e->n) if (e->to == father[now]) tree_key[C] = e->key; if (son[now]) Dfs_2 (son[now], point); else return ; for (e = list[now]; e; e = e->n) if (e->to != son[now] && e->to != father[now]) Dfs_2 (e->to, e->to); } public : void Prepare () { C = 0, Dfs_1 (1, 0), Dfs_2 (1, 1); Seg.Build (1, N); } int Query (int x, int y) { if (Ufs.Find (x) != Ufs.Find (y)) return -1; int res = INF; for (; chain[x] != chain[y]; ) { if (deep[chain[x]] < deep[chain[y]]) swap (x, y); res = min (Seg.Query (in[chain[x]], in[x]), res); x = father[chain[x]]; } if (deep[x] > deep[y]) swap (x, y); if (x != y) res = min (res, Seg.Query (in[x] + 1, in[y])); return res; } }; Tree_Chain_Get_Type T; int Main () { freopen ("truck.in", "r", stdin); freopen ("truck.ans", "w", stdout); fread (buf, 1, BUF, stdin); read (N), read (M); int x, y, z; register int i; for (i = 1; i <= M; ++ i) { read (x), read (y), read (z); data[i].from = x, data[i].to = y, data[i].key = z; } std :: sort (data + 1, data + 1 + M); int Count = 0; Ufs.Prepare (N); for (i = 1; i <= M; ++ i) { x = Ufs.Find (data[i].from), y = Ufs.Find (data[i].to); if (x != y) { ++ Tail, Tail->to = data[i].to, Tail->key = data[i].key; Tail->n = list[data[i].from], list[data[i].from] = Tail; ++ Tail, Tail->to = data[i].from, Tail->key = data[i].key; Tail->n = list[data[i].to], list[data[i].to] = Tail; ++ Count; Ufs.Unio (x, y); } if (Count == N - 1) break; } T.Prepare (); int Q; read (Q); for (i = 1; i <= Q; ++ i) read (x), read (y), printf ("%d ", T.Query (x, y)); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> const int BUF = 12312313; char Buf[BUF], *buf = Buf; inline void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } #define Max 1221313 int high[Max]; int Main () { freopen ("block.in", "r", stdin); freopen ("block.ans", "w", stdout); fread (buf, 1, BUF, stdin); int N, Answer = 0, Last = 0; read (N); register int i; for (i = 1; i <= N; ++ i) read (high[i]); for (i = 1; i <= N; ++ i) if (high[i] >= Last) { Answer += high[i] - Last; Last = high[i]; } else Last = high[i]; printf ("%d", Answer); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> const int BUF = 12312312; char Buf[BUF], *buf = Buf; inline void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } #define Max 120000 int Main () { freopen ("flower.in", "r", stdin); freopen ("flower.ans", "w", stdout); fread (buf, 1, BUF, stdin); int N, now, Answer = 0, res = 0, Last = 0; read (N); register int i; read (Last); for (i = 2; i <= N; Last = now, ++ i) { read (now); if (res == 0 && now - Last) ++ Answer, res = now - Last; else if (now - Last != 0 && res > 0 && now < Last) ++ Answer, res = now - Last; else if (res < 0 && now > Last && now - Last) ++ Answer, res = now - Last; } printf ("%d", Answer + 1); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <iostream> #include <cstring> #include <cstdio> #include <queue> struct Data { int x, y, a, b; int step; }Make; #define Max 31 const int BUF = 123123123; char Buf[BUF], *buf = Buf; inline void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } bool visit[Max][Max][Max][Max]; int map[Max][Max]; int N, M ,Q, Answer; int E_x, E_y, S_x, S_y, T_x, T_y; int move_x[5] = {0, 0, -1, 0, 1}; int move_y[5] = {0, -1, 0, 1, 0}; void Bfs () { std :: queue <Data> Queue; Data now, pos; int a,b; register int k; memset (visit, false, sizeof visit); visit[S_x][S_y][E_x][E_y] = true; for (Queue.push (Make); !Queue.empty(); Queue.pop ()) { now = Queue.front(); if (now.a == T_x && now.b == T_y) { Answer=now.step; return ; } for (k = 1; k <= 4; ++ k) { pos = now; a = pos.x + move_x[k]; b = pos.y + move_y[k]; if (a == pos.a && b == pos.b) pos.a = pos.x, pos.b = pos.y; if(!map[a][b] || a < 1 || a > N || b < 1 || b > M) continue ; pos.x = a, pos.y = b, ++ pos.step; if (!visit[pos.a][pos.b][pos.x][pos.y]) { Queue.push (pos); visit[pos.a][pos.b][pos.x][pos.y] = true; } } } } int Main () { freopen ("puzzle.in", "r", stdin); freopen ("puzzle.ans", "w", stdout); fread (buf, 1, BUF, stdin); read (N), read (M), read (Q); register int i, j; for (i = 1; i <= N; ++ i) for (j = 1; j <= M; ++ j) read (map[i][j]); for (; Q; -- Q) { Answer = N * M; read (E_x), read (E_y), read (S_x), read (S_y); read (T_x), read (T_y), Make.x = E_x, Make.y = E_y; Make.a = S_x, Make.b = S_y, Make.step = 0; if (S_x == T_x && S_y == T_y) { printf("0 "); continue ; } Bfs (); if (Answer != N * M) printf ("%d ", Answer); else printf ("-1 "); } return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> const int BUF = 12312312; char Buf[BUF], *buf = Buf; inline void read (int &now) { bool temp = false; for (now = 0; !isdigit (*buf); ++ buf) if (*buf == '-') temp = true; for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); if (temp) now = -now; } #define Max 100050 double _x[Max], _y[Max]; double i2[Max], _i[Max]; struct S_D { S_D *Left, *Right; double x, x2, y, xy, ss, st, ts, tt; int l, r, Mid; bool tag; S_D (int _l, int _r) { x = x2 = ss = st = ts = tt = y = xy = 0; Left = Right = NULL; l = _l, r = _r, Mid = l + r >> 1; tag = false; } inline void Up () { x = Left->x + Right->x, xy = Left->xy + Right->xy; y = Left->y + Right->y; x2 = Left->x2 + Right->x2; } inline void Down () { S_D *L = Left, *R = Right; double ls = L->r - L->l + 1, rs = R->r - R->l + 1; if (tag) { L->x = ts * ls + _i[L->r] - _i[L->l - 1]; L->y = tt * ls + _i[L->r] - _i[L->l - 1]; L->xy = ts * tt * ls + (_i[L->r] - _i[L->l - 1]) * (ts + tt) + i2[L->r] - i2[L->l - 1]; L->x2 = ts * ts * ls + (_i[L->r] - _i[L->l - 1]) * ts * 2.0 + i2[L->r] - i2[L->l - 1]; R->x = ts * rs + _i[R->r] - _i[R->l - 1]; R->y = tt * rs + _i[R->r] - _i[R->l - 1]; R->xy = ts * tt * rs + (_i[R->r] - _i[R->l - 1]) * (ts + tt) + i2[R->r] - i2[R->l - 1]; R->x2 = ts * ts * rs + (_i[R->r] - _i[R->l - 1]) * ts * 2.0 + i2[R->r] - i2[R->l - 1]; L->ts = R->ts = ts, L->tt = R->tt = tt; L->ss = R->st = L->st = R->ss = 0; tt = ts = 0, tag = false; L->tag = R->tag = true; } if (ss || st) { L->xy += st * L->x + ss * L->y + ss * st * ls; L->x2 += ss * L->x + ss * L->x + ss * ss * ls; R->xy += st * R->x + ss * R->y + ss * st * rs; R->x2 += ss * R->x + ss * R->x + ss * ss * rs; L->x += ss * ls, R->x += ss * rs; L->y += st * ls, L->y += st * rs; L->ss += ss, R->ss += ss; L->st += st, R->st += st; ss = st = 0; } } }; struct D { double x, y, x2, xy; D () : x (0), y (0), x2 (0), xy (0) {} D (double a, double b, double c, double d) : x (a), y (b), x2 (c), xy (d) {} }; #define DE printf ("%lf %lf %lf %lf ", now->x, now->y, now->x2, now->xy); class Segment_Tree { private : S_D *Root; void Build (S_D *&now, int l, int r) { now = new S_D (l, r); if (l == r) { now->x = (double)_x[l], now->y = (double)_y[r]; now->x2 = now->x * now->x; now->xy = now->x * now->y; return ; } Build (now->Left, l, now->Mid); Build (now->Right, now->Mid + 1, r); now->Up (); } void Change_1 (S_D *&now, int l, int r, double s, double t) { if (l <= now->l && now->r <= r) { double L = (now->r - now->l + 1); now->xy += t * now->x + s * now->y + s * t * L; now->x2 += s * now->x + s * now->x + s * s * L; now->x += s * L, now->y += t * L; now->ss += s, now->st += t; return ; } now->Down (); if (l <= now->Mid) Change_1 (now->Left, l, r, s, t); if (r > now->Mid) Change_1 (now->Right, l, r, s, t); now->Up (); } void Change_2 (S_D *&now, int l, int r, double s, double t) { if (l <= now->l && now->r <= r) { double L = (now->r - now->l + 1); now->tag = true; now->ss = now->st = 0, now->ts = s, now->tt = t; now->x = L * s + _i[now->r] - _i[now->l - 1]; now->y = L * t + _i[now->r] - _i[now->l - 1]; now->xy = L * s * t + (s + t) * (_i[now->r] - _i[now->l - 1]) + i2[now->r] - i2[now->l - 1]; now->x2 = L * s * s + 2 * s * (_i[now->r] - _i[now->l - 1]) + i2[now->r] - i2[now->l - 1]; return ; } now->Down (); if (l <= now->Mid) Change_2 (now->Left, l, r, s, t); if (r > now->Mid) Change_2 (now->Right, l, r, s, t); now->Up (); } D Query (S_D *&now, int l, int r) { if (l <= now->l && now->r <= r) return D (now->x, now->y, now->x2, now->xy); now->Down (); D A, B; if (l <= now->Mid) A = Query (now->Left, l, r); if (r > now->Mid) B = Query (now->Right, l, r); A.x += B.x, A.y += B.y; A.x2 += B.x2, A.xy += B.xy; return A; } public : inline void Build (int l, int r) { return Build (Root, l, r); } inline void Change_1 (int l, int r, double s, double t) { return Change_1 (Root, l, r, s, t); } inline void Change_2 (int l, int r, double s, double t) { return Change_2 (Root, l, r, s, t); } inline void Query (int l, int r) { D res = Query (Root, l, r); double s = r - l + 1; double b = res.xy - s * (res.x / s) * (res.y / s); b /= res.x2 - s * (res.x / s) * (res.x / s); printf ("%.10lf ", b); } }; Segment_Tree Seg; int Main () { fread (buf, 1, BUF, stdin); int N, M; read (N), read (M); register int i; int x; for (i = 1; i <= N; ++ i) read (x), _x[i] = (double) x; for (i = 1; i <= N; ++ i) read (x), _y[i] = (double) x; int type, y, s, t; for (i = 1; i <= N; ++ i) _i[i] = _i[i - 1] + i; for (i = 1; i <= N; ++ i) i2[i] = i2[i - 1] + i * i; Seg.Build (1, N); for (i = 1; i <= M; ++ i) { read (type); if (type == 1) { read (x), read (y); Seg.Query (x, y); } else if (type == 2) { read (x), read (y), read (s), read (t); Seg.Change_1 (x, y, (double) s, (double) t); } else if (type == 3) { read (x), read (y), read (s), read (t); Seg.Change_2 (x, y, (double) s, (double) t); } } return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> #include <cstring> const int BUF = 12312312; char Buf[BUF], *buf = Buf; #define Mod 20170408 inline void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } #define Max 20000007 #define L 100 struct Matrix { int c[L][L]; Matrix () { memset (c, 0, sizeof c); } Matrix operator * (const Matrix &now) const { Matrix res; for (register int i = 0, j, k; i < L; ++ i) for (k = 0; k < L; ++ k) if (this->c[i][k]) for (j = 0; j < L; ++ j) res.c[i][j] = (res.c[i][j] + 1LL * this->c[i][k] * now.c[k][j]) % Mod; return res; } }; int operator ^ (Matrix A, int p) { Matrix res; res.c[0][0] = 1; for (; p; A = A * A, p >>= 1) if (p & 1) res = res * A; return res.c[0][0]; } Matrix A; int prime[Max]; bool is[Max]; int C; void Euler (const int N) { is[1] = true; for (register int i = 2, j; i <= N; ++ i) { if (!is[i]) prime[++ C] = i; for (j = 1; i * prime[j] <= N && j <= C; ++ j) { is[i * prime[j]] = true; if (i % prime[j] == 0) break; } } } int data[Max]; int Main () { fread (buf, 1, BUF, stdin); int N, M, K; read (N), read (M), read (K); Euler (Max - 7); register int i, j; for (i = 1; i <= M; ++ i) ++ data[i % K]; for (i = 0; i < K; ++ i) for (j = 0; j < K; ++ j) A.c[i][(i + j) % K] = data[j] % Mod; int Answer = A ^ N; memset (A.c, 0, sizeof A.c); memset (data, 0, sizeof data); for (i = 1; i <= M; ++ i) if (is[i]) ++ data[i % K]; for (i = 0; i < K; ++ i) for (j = 0; j < K; ++ j) A.c[i][(i + j) % K] = data[j] % Mod; Answer -= A ^ N; printf ("%d", (Answer + Mod) % Mod); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> #include <algorithm> const int BUF = 12312312; char Buf[BUF], *buf = Buf; inline void read (int &now) { bool temp = false; for (now = 0; !isdigit (*buf); ++ buf) if (*buf == '-') temp = true; for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); if (temp) now = -now; } #define Max 800009 int x[Max], y[Max], s[Max]; int rank[Max], father[Max]; int Answer[Max], L, Stack[Max], top; int list[Max], next[Max]; int N, M; void Dfs (int now) { Stack[++ top] = now; if (now <= M) for (int i = L; ; ++ i) if (Stack[top - i] >= now + M) { Answer[now] = i; break; } for (int i = list[now]; i; i = next[i]) Dfs (i); -- top; } int Main () { freopen ("1.in", "r", stdin); fread (buf, 1, BUF, stdin); read (N), read (M); M = 0; register int i; for (i = 1; i <= N; ++ i) read (x[i]), read (y[i]), rank[++ M] = x[i], rank[++ M] = y[i]; std :: sort (rank + 1, rank + 1 + M); int Size = std :: unique (rank + 1, rank + 1 + M) - rank - 1; for (i = 1; i <= N; ++ i) { s[i] = x[i] = std :: lower_bound (rank + 1, rank + 1 + Size, x[i]) - rank; y[i] = std :: lower_bound (rank + 1, rank + 1 + Size, y[i]) - rank; if (x[i] < y[i]) { if (father[x[i]] < y[i]) father[x[i]] = y[i]; if (father[x[i] + M] < y[i] + M) father[x[i] + M] = y[i] + M; } else { if (father[1] < y[i]) father[1] = y[i]; if (father[x[i]] < y[i] + M) father[x[i]] = y[i] + M; if (father[x[i] + M] < (M << 1)) father[x[i] + M] = (M << 1); } } for (i = 1; i <= (M << 1); ++ i) if (father[i] < father[i - 1]) father[i] = father[i - 1]; for (i = 1; i < (M << 1); ++ i) next[i] = list[father[i]], list[father[i]] = i; for (L = -1, i = 1; i <= M; i = father[i]) ++ L; for (Dfs (M << 1), i = 1; i <= N; ++ i) printf ("%d ", Answer[s[i]]); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}
#include <cstdio> #include <iostream> #define Max 1000002 const int Mod = 1000000007; typedef long long LL; inline void read (LL &now) { register char c = getchar (); for (now = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); now = now * 10 + c - '0', c = getchar ()); } struct MT { #define L 2 #define Rg register int LL c[2][2]; MT operator * (const MT A) const { MT res; for (Rg i = 0, j, k; i < L; ++ i) for (j = 0; j < L; ++ j) { res.c[i][j] = 0; for (k = 0; k < L; ++ k) res.c[i][j] = (res.c[i][j] + c[i][k] * A.c[k][j]) % Mod; } return res; } #undef L }; LL operator ^ (MT A, register LL p) { MT res; res.c[0][0] = res.c[0][1] = res.c[1][0] = 1; res.c[1][1] = 0; if (p == 1 || p == 2) return 1; else if (p == 0) return 0; for (p -= 2; p; p >>= 1) { if (p & 1) res = res * A; A = A * A; } return res.c[0][0]; } #undef Rg LL Gcd (LL a, LL b) { return !b ? a : Gcd (b, a % b); } MT A; int Main () { freopen ("spfa.in", "r", stdin); freopen ("spfa.out", "w", stdout); LL N, M, P; read (N), read (M); register int i, j; P = Gcd (N, M); A.c[0][0] = A.c[0][1] = A.c[1][0] = 1, A.c[1][1] = 0; P = A ^ P; std :: cout << P; return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) { return 0; }
#include <cstdio> #include <iostream> #include <algorithm> #define Max 1200202 int c[Max]; inline void read (int &now) { register char c = getchar (); for (now = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); now = now * 10 + c - '0', ++ c); } int Main () { freopen ("small.in", "r", stdin); freopen ("small.out", "w", stdout); register int i; int N, T; read (T); for (i = 1; i <= T; ++ i) { read (N); for (i = 1; i <= N; ++ i) read (c[i]); std :: sort (c + 1, c + 1 + N); int S = std :: unique (c + 1, c + 1 + N) - c - 1; printf (S == N ? "Happy " : "Sad %d ", N - S); } } int ZlycerQan = Main (); int main (int argc, char *argv[]) { return 0; }
#include <cstdio> #define Max 1000002 int f[Max][2]; #define INF 1e8 int p[] = { 2, 3, 5, 7, 11 }; inline void min (int &a, int b) { if (b < a) a = b; return ;} int Dfs (int n, int t) { if (n == 1) return 0; if (f[n][t]) return f[n][t]; f[n][t] = INF; register int i; for (i = 0; i < 4; ++ i) if (!(n % p[i])) min (f[n][t], Dfs (n / p[i], 1) + p[i]); if (t == 0) return f[n][t]; f[n][0] = f[n][1]; for (i = 1; i <= 2; ++ i) min (f[n][t], Dfs (n + i, 0) + i); return f[n][t]; } int Main () { freopen ("huaji.in", "r", stdin); freopen ("huaji.out", "w", stdout); int N; scanf ("%d", &N); printf ("%d", Dfs (N, 1)); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) { return 0; }
#include <cstdio> #include <iostream> #include <cstdlib> #define rg register inline void read (int &now) { rg char c = getchar (); for (now = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); now = now * 10 + c - '0', c = getchar ()); } #define Max 1000009 int f[Max], N, B, T, x, y; int Find (int x) { return f[x] == x ? x : f[x] = Find (f[x]); } int main () { freopen ("dream.in", "r", stdin); freopen ("dream.out", "w", stdout); int i, j, a, b; for (read (T); T; -- T) { read (N), read (B), read (x), read (y); for (i = 1; i <= N; ++ i) f[i] = i; for (i = B + 1; i <= N; ++ i) for (j = i * 2; j <= N; j += i) { a = Find (i), b = Find (j); if (a != b) f[b] = a; } if (Find (x) == Find (y)) printf ("YeS "); else printf ("No "); } return 0; }
#include <cstdio> #include <iostream> #define rg register inline void read (int &now) { rg char c = getchar (); for (now = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); now = now * 10 + c - '0', c = getchar ()); } #define Max 100009 struct E { E *n; int v; } *list[Max], poor[Max << 1], *Ta = poor; int f[Max][Max / 5000 + 2], s[Max], fa[Max], v[Max], k; void Yukari (int n, int F) { fa[n] = F; for (E *e = list[n]; e; ++ v[n], e = e->n) if (e->v != F) Yukari (e->v, n); } void Dfs (int n) { for (E *e = list[n]; e; e = e->n) { int V; f[n][k] += f[V = e->v][k - 1]; if (V == fa[n]) continue; Dfs (V); } if (k > 2) f[n][k] -= f[n][k - 2] * (v[n] - 1); if (k == 2) f[n][k] -= f[n][0] * v[n]; s[n] += f[n][k]; } int Main () { freopen ("young.in", "r", stdin); freopen ("young.out", "w", stdout); int N, K, R, C, x, y; read (R), read (C), read (N), read (K); rg int i; for (i = 1; i < N; ++ i) { read (x), read (y); ++ Ta, Ta->v = y, Ta->n = list[x], list[x] = Ta; ++ Ta, Ta->v = x, Ta->n = list[y], list[y] = Ta; } Yukari (1, 0); for (i = 1; i <= N; ++ i) read (s[i]), f[i][0] = s[i]; for (i = 1; i <= K; ++ i) k = i, Dfs (1); for (i = 1; i <= N; ++ i) printf ("%d ", s[i]); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) { return 0; }
#include <cstdio> #include <iostream> #include <algorithm> #define rg register inline void read (int &now) { rg char c = getchar (); for (now = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); now = now * 10 + c - '0', c = getchar ()); } int Main () { freopen ("moon.in", "r", stdin); freopen ("moon.out", "w", stdout); int N; read (N); rg int i, j, Answer = 0; int x; for (i = 1; i <= N; ++ i) read (x), Answer -= x, read (x), Answer += x; for (i = 1; i <= N; ++ i) read (x), Answer += x, read (x), Answer -= x; printf ("%d", Answer); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) { return 0; }
#include <cstdio> #include <iostream> #include <algorithm> #define rg register inline void read (int &now) { rg char c = getchar (); for (now = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); now = now * 10 + c - '0', c = getchar ()); } int Main () { freopen ("moon.in", "r", stdin); freopen ("moon.out", "w", stdout); int N; read (N); rg int i, j, Answer = 0; int x; for (i = 1; i <= N; ++ i) read (x), Answer -= x, read (x), Answer += x; for (i = 1; i <= N; ++ i) read (x), Answer += x, read (x), Answer -= x; printf ("%d", Answer); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) { return 0; }
#include <cstdio> #include <iostream> #include <string> #include <cstring> #define rg register #define Max 1000 typedef long long LL; using std :: string; char l[Max]; int c[Max]; string Answer; int Main () { freopen ("hwc.in", "r", stdin); freopen ("hwc.out", "w", stdout); scanf ("%s", l); rg int i, j; int Len = strlen (l); for (i = Len - 1; i >= 0; -- i) { c[i + 1] = l[i] - '0' + c[i + 2] / 10, c[i + 2] %= 10; if (i == Len - 1) ++ c[i + 1]; if (i == 0) -- c[i + 1]; } bool f = false, p = false, e = false; for (i = 1; i <= Len; ++ i) { if (!c[i] && i == 1) { f = true; continue; } else if (!c[i] && i == 2 && f) p = true, Answer.push_back ('9'); else Answer.push_back (c[i] + '0'); } if (f && !p) e = true; else -- Len; for (i = Len; i >= 1; -- i) { if (!c[i] && i == 1) continue; else if (!c[i] && i == 2 && f) Answer.push_back ('9'); else Answer.push_back (c[i] + '0'); } std :: cout << Answer; return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) { return 0; }
#include <cstdio> #include <iostream> #include <cstring> #define rg register #define EPS 1e-3 #define INF 1e7 typedef double flo; const int BUF = 12312323; char Buf[BUF], *buf = Buf; inline void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } #define Max 1010 struct E { E *n; int v, d; } *list[Max], poor[Max * 6], *Ta = poor; flo d[Max]; bool is[Max]; int c[Max]; bool Check (int n, flo key) { is[n] = true; for (E *e = list[n]; e; e = e->n) { int V; flo r = c[(V = e->v)] - key * e->d; if (d[V] < d[n] + r) if (!is[V]) { d[V] = d[n] + r; if (Check (V, key)) return true; } else return true; } return is[n] = false; } int Main () { fread (buf, 1, BUF, stdin); int N, M, x, y, z; read (N), read (M); rg int i, j; flo Answer; for (i = 1; i <= N; ++ i) read (c[i]); for (i = 1; i <= M; ++ i) { read (x), read (y), read (z); ++ Ta, Ta->v = y, Ta->n = list[x], list[x] = Ta, Ta->d = z; } for (flo Mid, l = 0, r = 1000.0; r - l > EPS; ) { Mid = (l + r) / 2.0; for (i = 1; i <= N; ++ i) d[i] = -INF; memset (is, false, sizeof is); d[1] = 0.0; if (Check (1, Mid)) l = Mid, Answer = Mid; else r = Mid; } printf ("%.2lf", Answer); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) { return 0; }
#include <cstdio> #include <iostream> #define rg register #define INF 1e8 void read (int &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } #define Max 100005 struct SD { SD *L, *R; int v, k, Mid, l, r; void Up () { v = L->v | R->v; } } poor[Max << 2], *null, *Ta = poor; int a[Max], N, M, A, B; class SegmentTree { private : SD *Root; private : SD *New (int x, int y) { ++ Ta, Ta->L = Ta->R = null; Ta->v = 0; Ta->Mid = x + y >> 1; Ta->l = x, Ta->r = y; return Ta; } void Build (SD *&n, int l, int r) { n = New (l, r); if (l == r) { n->v = 1; return ; } Build (n->L, l, n->Mid); Build (n->R, n->Mid + 1, r); n->k = 3; n->Up (); } void C (SD *&n, int p, int k) { if (n->l == n->r) { n->v = k; return ; } if (p <= n->Mid) C (n->L, p, k); else C (n->R, p, k); n->Up (); if (n->v) { if (n->L->v && n->R->v) n->k = 3; else if (n->L->v) n->k = 1; else n->k = 2; return ; } n->k = 0; } int Q (SD *&n, int l, int r) { if (n->v == 0) return INF; int s = INF; if (l <= n->l && n->r <= r) { if (n->l == n->r) return n->l; if (n->k == 1 || n->k == 3) { s = Q (n->L, l, r); if (s != INF) return s; } if (n->k == 2 || n->k == 3) { s = Q (n->R, l, r); if (s != INF) return s; } return s; } if (l <= n->Mid && (n->k == 1 || n->k == 3)) { s = Q (n->L, l, r); if (s != INF) return s; } if (r > n->Mid && (n->k == 2 || n->k == 3)) { s = Q (n->R, l, r); if (s != INF) return s; } return INF; } public : inline void Build (int l, int r) { Build (Root, l, r); C (a[1], 0), C (a[2], 0); } inline void C (int p, int k) { return C (Root, p, k); } inline int Q (int l, int r) { return Q (Root, l, r); } }; SegmentTree Seg; int main (int argc, char *argv[]) { freopen ("lunch.in", "r", stdin); freopen ("lunch.out", "w", stdout); rg int i, j; read (N), read (M), read (A), read (B), read (a[1]), read (a[2]); null = Ta; null->L = null->R = null; null->l = null->r = null->v = null->k = null->Mid = 0; Seg.Build (0, N - 1); int li = 1, ri = N / 2, r; for (i = 3; i <= M; ++ i) { for (; i - li > ri; Seg.C (a[li ++], 1)); a[i] = (1LL * A * a[i - 1] + 1LL * B * a[i - 2]) % N; r = Seg.Q (a[i], N - 1); if (r != INF) { a[i] = r; Seg.C (a[i], 0); } else { a[i] = Seg.Q (0, a[i] - 1); Seg.C (a[i], 0); } printf ("%d ", a[i]); } fclose (stdin); fclose (stdout); return 0; }
#include <cstdio> #include <iostream> #include <cstring> #define rg register inline void read (int &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } #define Max 1000005 struct E { E *n; int v; } *list[Max], poor[Max << 1], *Ta = poor; int m[Max], _m[Max], l[Max], Maxn, MaxP, Answer; bool is[Max]; void Dfs (int n, int F) { for (E *e = list[n]; e; e = e->n) if (e->v != F) l[e->v] = l[n] + 1, Dfs (e->v, n); if (l[n] > Maxn) Maxn = l[n], MaxP = n; } int pre[Max]; void _Dfs (int n, int F) { for (E *e = list[n]; e; e = e->n) if (e->v != F) l[e->v] = l[n] + 1, _Dfs (e->v, n), pre[e->v] = n; if (l[n] > Maxn) Maxn = l[n], MaxP = n; } inline void max (int &a, int b) { if (b > a) a = b; } void Get (int n) { for (E *e = list[n]; e; e = e->n) if (!is[e->v]) l[e->v] = l[n] + 1, is[e->v] = true, Get (e->v); max (Answer, l[n]); } int main (int argc, char *argv[]) { freopen ("tree.in", "r", stdin); freopen ("tree.out", "w", stdout); rg int i, j; int N, x, y; read (N); for (i = 1; i < N; ++ i) { read (x), read (y); ++ Ta, Ta->v = y, Ta->n = list[x], list[x] = Ta; ++ Ta, Ta->v = x, Ta->n = list[y], list[y] = Ta; } Dfs (1, 0); memset (l, 0, sizeof l); Maxn = 0; int S = MaxP; _Dfs (MaxP, 0); for (i = MaxP, is[S] = true; i != S; i = pre[i]) is[i] = true; memset (l, 0, sizeof l); for (i = 1; i <= N; ++ i) if (is[i]) Get (i); printf ("%d", Answer); fclose (stdin); fclose (stdout); return 0; }
#include <cstdio> #include <iostream> #include <cmath> #include <algorithm> #define rg register inline void read (int &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } int N, M, Q; #define Max 200009 int c[Max], b[Max], key[Max], Answer; struct Q { int id, l, r; bool operator < (const Q &A) const { return b[l] == b[A.l] ? r < A.r : b[l] < b[A.l]; } } q[Max]; int Zly[Max]; void make (int n, int k, bool t) { key[c[n]] += k; if (t) { if (c[n] < Answer && !key[c[n]] && !key[c[n] + 1]) Answer = c[n]; if (c[n] - 1 < Answer && !key[c[n] - 1] && !key[c[n]] && c[n] - 1 != 0) Answer = c[n] - 1; } else if (c[n] == Answer || c[n] == Answer + 1) for (; key[Answer] || key[Answer + 1]; ++ Answer); } int main (int argc, char *argv[]) { freopen ("stall.in", "r", stdin); freopen ("stall.out", "w", stdout); read (N), read (M), read (Q); int K_Size = sqrt (M); rg int i; for (i = 1; i <= M; ++ i) read (c[i]), b[i] = (i + 1) / K_Size; for (i = 1; i <= Q; ++ i) q[i].id = i, read (q[i].l), read (q[i].r); std :: sort (q + 1, q + 1 + Q); int l = 1, r = 0; Answer = 1; for (i = 1; i <= Q; ++ i) { for (; l < q[i].l; make (l ++, -1, true)); for (; l > q[i].l; make (-- l, 1, false)); for (; r < q[i].r; make (++ r, 1, false)); for (; r > q[i].r; make (r --, -1, true)); Zly[q[i].id] = Answer; if (Answer > N) Zly[q[i].id] = -1; } for (i = 1; i <= Q; ++ i) { if (Zly[i] == -1) printf ("-1 -1 "); else printf ("%d %d ", Zly[i], Zly[i] + 1); } fclose (stdin); fclose (stdout); return 0; }
#include <iostream> #include <cstdio> #include <cstring> #define rg register #define Max 10005 int N, M, C, Scc, ind, top, v[Max],w[Max], sv[Max],sw[Max]; bool in_stack[Max]; int dfn[Max],low[Max],belong[Max], stack[Max],f[Max][2505],in[2505]; inline int min (int a, int b) { return a < b ? a : b; } inline int max (int a, int b) { return a > b ? a : b; } struct E { E *n; int v; } *list1[Max * 10], poor[Max * 20], *Ta = poor, *list2[Max * 10]; inline int read (int &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } void Tarjan (int u) { int now = 0; E *e; dfn[u] = low[u] = ++ ind, stack[++ top] = u, in_stack[u] = 1; for (e = list1[u]; e; e = e->n) { int v = e->v; if (!dfn[v]) Tarjan(v), low[u] = min (low[u], low[v]); else if (in_stack[v]) low[u] = min (low[u], dfn[v]); } if (low[u] == dfn[u]) for (++ Scc; now != u; ) { now = stack[top --]; in_stack[now] = 0; belong[now] = Scc, sw[Scc] += w[now], sv[Scc] += v[now]; } } void dp(int x) { rg int i, j, k; E *e; for (e = list2[x]; e; e = e->n) { dp (e->v); for (j = M - sw[x]; j >= 0; -- j) for (k = 0; k <= j; ++ k) f[x][j] = max (f[x][j], f[x][k] + f[e->v][j - k]); } for (j = M; j >= 0; -- j) { if (j >= sw[x]) f[x][j] = f[x][j - sw[x]] + sv[x]; else f[x][j]=0; } } int main (int argc, char *argv[]) { freopen ("T1.in", "r", stdin); freopen ("T1.out", "w", stdout); int x; read (N), read (M); rg int i; E *e; for (i = 1; i <= N; ++ i) read (w[i]); for (i = 1; i <= N; ++ i) read (v[i]); for (i = 1; i <= N; ++ i) { read (x); if (x) ++ Ta, Ta->v = i, Ta->n = list1[x], list1[x] = Ta; } for (i = 1; i <= N; ++ i) if (!dfn[i]) Tarjan (i); int v; for (x = 1; x <= N; ++ x) for (e = list1[x]; e; e = e->n) if (belong[(v = e->v)] != belong[x]) ++ Ta, Ta->v = belong[v], Ta->n = list2[belong[x]], list2[belong[x]] = Ta, in[belong[v]] = 1; for (i = 1; i <= Scc; ++ i) if(!in[i]) ++ Ta, Ta->v = i, Ta->n = list2[Scc + 1], list2[Scc + 1] = Ta, in[i] = 1; dp (Scc + 1); printf ("%d ", f[Scc + 1][M]); return 0; }
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define Max 400010 #define INF 233333333 int head[Max], nxt[Max], to[Max], tot = 0, num[Max]; inline int min (int a, int b) { return a < b ? a : b; } inline int max (int a, int b) { return a > b ? a : b; } int maxn[Max][30],minn[Max][30],anc[Max][30],ans1[Max][30],ans2[Max][30], deep[Max]; const int BUF = 12312323; char Buf[BUF], *buf = Buf; void read (int &n) { for (n = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); n = n * 10 + *buf - '0', ++ buf); } inline void cmax (int &a, int b) { if (b > a) a = b; } inline void cmin (int &a, int b) { if (b < a) a = b; } class SegmentTree { private : struct SD { SD *L, *R; int vu, vd, mx, mn, l, r, Mid; inline void Up () { mx = max (L->mx, R->mx), mn = min (L->mn, R->mn); vu = R->mx - L->mn, vd = L->mx - R->mn; } } *Root, poor_T[Max << 2], *TT; inline SD* New (int x, int y) { ++ TT, TT->l = x, TT->r = y, TT->Mid = x + y >> 1; TT->mx = TT->mn = TT->vu = TT->vd = 0; TT->L = TT->R = NULL; return TT; } void Build (SD *&n, int l, int r) { n = New (l, r); if (l == r) { n->mx = n->mn = 0; return ; } Build (n->L, l, n->Mid), Build (n->R, n->Mid + 1, r); n->Up (); } int Q (SD *&n, int l, int r, bool t) { if (l <= n->l && n->r <= r) { if (t) return n->mx; return n->mn; } int A = 0; if (l <= n->Mid) A = Q (n->L, l, r, t); if (r > n->Mid) { if (t) cmax (A, Q (n->R, l, r, t)); else cmin (A, Q (n->R, l, r, t)); }; return A; } public : SegmentTree () { TT = poor_T; } void Build (int l, int r) { return Build (Root, l, r); } int Q_max (int l, int r) { return Q (Root, l, r, true); } int Q_min (int l, int r) { return Q (Root, l, r, false); } }; inline void build (int f, int t) { to[++tot]=t, nxt[tot]=head[f], head[f]=tot; } void dfs (int u, int fa) { if(deep[u]) return ; register int i; deep[u] = deep[fa]+1; minn[u][0] = min (num[u], num[fa]); maxn[u][0] = max (num[u], num[fa]); ans1[u][0] = max (0, num[u] - num[fa]); ans2[u][0] = max (0, num[fa] - num[u]); anc[u][0] = fa; for(int i=1;anc[u][i - 1];i++) { anc[u][i] = anc[anc[u][i - 1]][i - 1]; maxn[u][i] = max (maxn[u][i - 1], maxn[anc[u][i - 1]][i - 1]); minn[u][i] = min (minn[u][i - 1], minn[anc[u][i - 1]][i - 1]); ans1[u][i] = max (max (ans1[u][i - 1], ans1[anc[u][i - 1]][i - 1]), maxn[u][i - 1] - minn[anc[u][i - 1]][i - 1]); ans2[u][i] = max (max (ans2[u][i - 1], ans2[anc[u][i - 1]][i - 1]), maxn[anc[u][i - 1]][i - 1] - minn[u][i - 1]); } for (i = head[u]; i; i = nxt[i]) dfs(to[i],u); } inline void swap (int &a, int &b) { int c = a; a = b, b = c; } int asklca (int x, int y) { int ans = 0; register int i; if(deep[x]<deep[y]) swap(x,y); if (deep[x] > deep[y]) { int dd = deep[x] - deep[y]; for(i = 24; i >= 0; -- i) if (dd & (1 << i)) x = anc[x][i]; } if (x != y) for(i = 24; i >= 0; -- i) if(anc[x][i] != anc[y][i]) x = anc[x][i], y = anc[y][i]; if (x == y) return x; else return anc[x][0]; } int ask (int x, int y) { int lca = asklca(x,y); int maxx = -INF, minnn = INF, ans = 0; int dd1 = deep[x] - deep[lca]; if (dd1 > 0) for (int i = 24; i >= 0; -- i) if (dd1 & (1 << i)) { ans = max (ans, max (ans2[x][i], maxn[x][i] - minnn)); minnn = min (minn[x][i], minnn); x = anc[x][i]; } int dd2 = deep[y] - deep[lca]; if (dd2 > 0) for (int i = 24; i >= 0; -- i) if (dd2 & (1 << i)) { ans = max (ans, max (ans1[y][i], maxx - minn[y][i])); maxx = max (maxn[y][i], maxx); y = anc[y][i]; } return max (ans, maxx - minnn); } int main (int argc, char *argv[]) { freopen ("T2.in", "r", stdin); freopen ("T2.out", "w", stdout); register int i, j; fread (buf, 1, BUF, stdin); int n; read (n); for (i = 1; i <= n; ++ i) read (num[i]); for (i = 1;i < n; ++ i) { int a,b; read (a), read (b); build(a,b); build(b,a); } dfs(1,0); int q; read (q); for (int x, y; q --; ) read (x), read (y), printf("%d ",ask(x,y)); return 0; }
跪膜myj%%%%%%%
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int INF=0x3f3f3f3f; int n,m,q,p,sx,sy,sz,sd,ex,ey,ez,ed,ans; bool vis[23][23][23]; inline void in(int &now) { char Cget;now=0;while((Cget=getchar())>'9'||Cget<'0'); while(Cget>='0'&&Cget<='9')now=now*10+Cget-'0',Cget=getchar(); } void dfs(int x,int y,int z,int d,int step) { if(step>=ans) return; if(x==ex&&ey==y&&ez==z&&d==ed) { ans=step; return; } if(step==12) return; if(x==ex&&y==ey&&z==ez) return; if(abs(ex-x)+abs(ey-y)+abs(ez-z)>(ans-step)*4) return; if(d==1) { if(z+2<=q) if(!vis[x][y][z+1]&&!vis[x][y][z+2]) { vis[x][y][z+1]=vis[x][y][z+2]=true; if(y+2<=m) if(!vis[x][y+1][z+2]&&!vis[x][y+2][z+2]) { vis[x][y+1][z+2]=vis[x][y+2][z+2]=true; dfs(x,y+2,z+2,5,step+1); vis[x][y+1][z+2]=vis[x][y+2][z+2]=false; } if(y-2>=1) if(!vis[x][y-1][z+2]&&!vis[x][y-2][z+2]) { vis[x][y-1][z+2]=vis[x][y-2][z+2]=true; dfs(x,y-2,z+2,2,step+1); vis[x][y-1][z+2]=vis[x][y-2][z+2]=false; } if(x+2<=n) if(!vis[x+1][y][z+2]&&!vis[x+2][y][z+2]) { vis[x+1][y][z+2]=vis[x+2][y][z+2]=true; dfs(x+2,y,z+2,3,step+1); vis[x+1][y][z+2]=vis[x+2][y][z+2]=false; } if(x-2>=1) if(!vis[x-1][y][z+2]&&!vis[x-2][y][z+2]) { vis[x-1][y][z+2]=vis[x-2][y][z+2]=true; dfs(x-2,y,z+2,6,step+1); vis[x-1][y][z+2]=vis[x-2][y][z+2]=false; } vis[x][y][z+1]=vis[x][y][z+2]=false; } if(z-1>=1) if(!vis[x][y][z-1]&&!vis[x][y][z]) { vis[x][y][z]=vis[x][y][z-1]=true; if(y+2<=m) if(!vis[x][y+1][z-1]&&!vis[x][y+2][z-1]) { vis[x][y+1][z-1]=vis[x][y+2][z-1]=true; dfs(x,y+2,z-1,5,step+1); vis[x][y+1][z-1]=vis[x][y+2][z-1]=false; } if(y-2>=1) if(!vis[x][y-1][z-1]&&!vis[x][y-2][z-1]) { vis[x][y-1][z-1]=vis[x][y-2][z-1]=true; dfs(x,y-2,z-1,2,step+1); vis[x][y-1][z-1]=vis[x][y-2][z-1]=false; } if(x+2<=n) if(!vis[x+1][y][z-1]&&!vis[x+2][y][z-1]) { vis[x+1][y][z-1]=vis[x+2][y][z-1]=true; dfs(x+2,y,z-1,3,step+1); vis[x+1][y][z-1]=vis[x+2][y][z-1]=false; } if(x-2>=1) if(!vis[x-1][y][z-1]&&!vis[x-2][y][z-1]) { vis[x-1][y][z-1]=vis[x-2][y][z-1]=true; dfs(x-2,y,z-1,6,step+1); vis[x-1][y][z-1]=vis[x-2][y][z-1]=false; } vis[x][y][z]=vis[x][y][z-1]=false; } if(z+3<=q) if(!vis[x][y][z+1]&&!vis[x][y][z+2]&&!vis[x][y][z+3]) { vis[x][y][z+1]=vis[x][y][z+2]=vis[x][y][z+3]=true; if(y+1<=m) if(!vis[x][y+1][z+3]) { vis[x][y+1][z+3]=true; dfs(x,y+1,z+3,5,step+1); vis[x][y+1][z+3]=false; } if(y-1<=m) if(!vis[x][y-1][z+3]) { vis[x][y-1][z+3]=true; dfs(x,y-1,z+3,2,step+1); vis[x][y-1][z+3]=false; } if(x+1<=m) if(!vis[x+1][y][z+3]) { vis[x+1][y][z+3]=true; dfs(x+1,y,z+3,3,step+1); vis[x+1][y][z+3]=false; } if(x-1<=m) if(!vis[x-1][y][z+3]) { vis[x-1][y][z+3]=true; dfs(x-1,y,z+3,6,step+1); vis[x-1][y][z+3]=false; } vis[x][y][z+1]=vis[x][y][z+2]=vis[x][y][z+3]=false; } if(z-2>=1) if(!vis[x][y][z]&&!vis[x][y][z-1]&&!vis[x][y][z-2]) { vis[x][y][z]=vis[x][y][z-1]=vis[x][y][z-2]=true; if(y+1<=m) if(!vis[x][y+1][z-2]) { vis[x][y+1][z-2]=true; dfs(x,y+1,z-2,5,step+1); vis[x][y+1][z-2]=false; } if(y-1<=m) if(!vis[x][y-1][z-2]) { vis[x][y-1][z-2]=true; dfs(x,y-1,z-2,2,step+1); vis[x][y-1][z-2]=false; } if(x+1<=m) if(!vis[x+1][y][z-2]) { vis[x+1][y][z-2]=true; dfs(x+1,y,z-2,3,step+1); vis[x+1][y][z-2]=false; } if(x-1<=m) if(!vis[x-1][y][z-2]) { vis[x-1][y][z-2]=true; dfs(x-1,y,z-2,6,step+1); vis[x-1][y][z-2]=false; } vis[x][y][z]=vis[x][y][z-2]=vis[x][y][z-1]=false; } } if(d==2) { if(y+1<=m) if(!vis[x][y][z]&&!vis[x][y+1][z]) { vis[x][y][z]=vis[x][y+1][z]=true; if(z+2<=q) if(!vis[x][y+1][z+2]&&!vis[x][y+1][z+1]) { vis[x][y+1][z+2]=vis[x][y+1][z+1]=true; dfs(x,y+1,z+2,1,step+1); vis[x][y+1][z+2]=vis[x][y+1][z+1]=false; } if(z-2>=1) if(!vis[x][y+1][z-1]&&!vis[x][y+1][z-2]) { vis[x][y+1][z-1]=vis[x][y+1][z-2]=true; dfs(x,y+1,z-2,4,step+1); vis[x][y+1][z-1]=vis[x][y+1][z-2]=false; } if(x+2<=n) if(!vis[x+1][y+1][z]&&!vis[x+2][y+1][z]) { vis[x+1][y+1][z]=vis[x+2][y+1][z]=true; dfs(x+2,y+1,z,3,step+1); vis[x+1][y+1][z]=vis[x+2][y+1][z]=false; } if(x-2>=1) if(!vis[x-1][y+1][z]&&!vis[x-2][y+1][z]) { vis[x-1][y+1][z]=vis[x-2][y+1][z]=true; dfs(x-2,y+1,z,6,step+1); vis[x-1][y+1][z]=vis[x-2][y+1][z]=false; } vis[x][y][z]=vis[x][y+1][z]=false; } if(y-2>=1) if(!vis[x][y-1][z]&&!vis[x][y-2][z]) { vis[x][y-1][z]=vis[x][y-2][z]=true; if(z+2<=q) if(!vis[x][y-2][z+1]&&!vis[x][y-2][z+2]) { vis[x][y-2][z+1]=vis[x][y-2][z+2]=true; dfs(x,y-2,z+2,1,step+1); vis[x][y-2][z+1]=vis[x][y-2][z+2]=false; } if(z-2>=1) if(!vis[x][y-2][z-1]&&!vis[x][y-2][z-2]) { vis[x][y-2][z-1]=vis[x][y-2][z-2]=true; dfs(x,y-2,z-2,4,step+1); vis[x][y-2][z-1]=vis[x][y-2][z-2]=false; } if(x+2<=n) if(!vis[x+1][y-2][z]&&!vis[x+2][y-2][z]) { vis[x+1][y-2][z]=vis[x+2][y-2][z]=true; dfs(x+2,y-2,z,3,step+1); vis[x+1][y-2][z]=vis[x+2][y-2][z]=false; } if(x-2>=1) if(!vis[x-1][y-2][z]&&!vis[x-2][y-2][z]) { vis[x-1][y-2][z]=vis[x-2][y-2][z]=true; dfs(x-2,y-2,z,6,step+1); vis[x-1][y-2][z]=vis[x-2][y-2][z]=false; } vis[x][y-1][z]=vis[x][y-2][z]=false; } if(y+2<=m) if(!vis[x][y][z]&&!vis[x][y+1][z]&&!vis[x][y+2][z]) { vis[x][y][z]=vis[x][y+1][z]=vis[x][y+2][z]=true; if(z+1<=q) if(!vis[x][y+2][z+1]) { vis[x][y+2][z+1]=true; dfs(x,y+2,z+1,1,step+1); vis[x][y+2][z+1]=false; } if(z-1>=1) if(!vis[x][y+2][z-1]) { vis[x][y+2][z-1]=true; dfs(x,y+2,z-1,4,step+1); vis[x][y+2][z-1]=false; } if(x+1<=n) if(!vis[x+1][y+2][z]) { vis[x+1][y+2][z]=true; dfs(x+1,y+2,z,3,step+1); vis[x+1][y+2][z]=false; } if(x-1>=1) if(!vis[x-1][y+2][z]) { vis[x-1][y+2][z]=true; dfs(x-1,y+2,z,6,step+1); vis[x-1][y+2][z]=false; } vis[x][y][z]=vis[x][y+1][z]=vis[x][y+2][z]=false; } if(y-3>=1) if(!vis[x][y-1][z]&&!vis[x][y-2][z]&&!vis[x][y-3][z]) { vis[x][y-1][z]=vis[x][y-2][z]=vis[x][y-3][z]=true; if(z+1<=q) if(!vis[x][y-3][z+1]) { vis[x][y-3][z+1]=true; dfs(x,y-3,z+1,1,step+1); vis[x][y-3][z+1]=false; } if(z-1>=1) if(!vis[x][y-3][z-1]) { vis[x][y-3][z-1]=true; dfs(x,y-3,z-1,4,step+1); vis[x][y-3][z-1]=false; } if(x+1<=n) if(!vis[x+1][y-3][z]) { vis[x+1][y-3][z]=true; dfs(x+1,y-3,z,3,step+1); vis[x+1][y-3][z]=false; } if(x-1>=1) if(!vis[x-1][y-3][z]) { vis[x-1][y-3][z]=true; dfs(x-1,y-3,z,6,step+1); vis[x-1][y-3][z]=false; } vis[x][y-1][z]=vis[x][y-2][z]=vis[x][y-3][z]=false; } } if(d==3) { if(x+2<=n) if(!vis[x+1][y][z]&&!vis[x+2][y][z]) { vis[x+1][y][z]=vis[x+2][y][z]=true; if(z+2<=q) if(!vis[x+2][y][z+1]&&!vis[x+2][y][z+2]) { vis[x+2][y][z+1]=vis[x+2][y][z+2]=true; dfs(x+2,y,z+2,1,step+1); vis[x+2][y][z+1]=vis[x+2][y][z+2]=false; } if(z-2>=1) if(!vis[x+2][y][z-1]&&!vis[x+2][y][z-2]) { vis[x+2][y][z-1]=vis[x+2][y][z-2]=true; dfs(x+2,y,z-2,4,step+1); vis[x+2][y][z-1]=vis[x+2][y][z-2]=false; } if(y+2<=m) if(!vis[x+2][y+1][z]&&!vis[x+2][y+2][z]) { vis[x+2][y+1][z]=vis[x+2][y+2][z]=true; dfs(x+2,y+2,z,5,step+1); vis[x+2][y+1][z]=vis[x+2][y+2][z]=false; } if(y-2>=1) if(!vis[x+2][y-1][z]&&!vis[x+2][y-2][z]) { vis[x+2][y-1][z]=vis[x+2][y-2][z]=true; dfs(x+2,y-2,z,2,step+1); vis[x+2][y-1][z]=vis[x+2][y-2][z]=false; } vis[x+1][y][z]=vis[x+2][y][z]=false; } if(x-1>=1) if(!vis[x][y][z]&&!vis[x-1][y][z]) { vis[x][y][z]=vis[x-1][y][z]=true; if(z+2<=q) if(!vis[x-1][y][z+1]&&!vis[x-1][y][z+2]) { vis[x-1][y][z+1]=vis[x-1][y][z+2]=true; dfs(x-1,y,z+2,1,step+1); vis[x-1][y][z+1]=vis[x-1][y][z+2]=false; } if(z-2>=1) if(!vis[x-1][y][z-1]&&!vis[x-1][y][z-2]) { vis[x-1][y][z-1]=vis[x-1][y][z-2]=true; dfs(x-1,y,z-2,4,step+1); vis[x-1][y][z-1]=vis[x-1][y][z-2]=false; } if(y+2<=m) if(!vis[x-1][y+1][z]&&!vis[x-1][y+2][z]) { vis[x-1][y+1][z]=vis[x-1][y+2][z]=true; dfs(x-1,y+2,z,5,step+1); vis[x-1][y+1][z]=vis[x-1][y+2][z]=false; } if(y-2>=1) if(!vis[x-1][y-1][z]&&!vis[x-1][y-2][z]) { vis[x-1][y-1][z]=vis[x-1][y-2][z]=true; dfs(x-1,y-2,z,2,step+1); vis[x-1][y-1][z]=vis[x-1][y-2][z]=false; } vis[x][y][z]=vis[x-1][y][z]=false; } if(x+3<=n) if(!vis[x+1][y][z]&&!vis[x+2][y][z]&&!vis[x+3][y][z]) { vis[x+1][y][z]=vis[x+2][y][z]=vis[x+3][y][z]=true; if(y+1<=m) if(!vis[x+3][y+1][z]) { vis[x+3][y+1][z]=true; dfs(x+3,y+1,z,5,step+1); vis[x+3][y+1][z]=false; } if(y-1>=1) if(!vis[x+3][y-1][z]) { vis[x+3][y-1][z]=true; dfs(x+3,y-1,z,2,step+1); vis[x+3][y-1][z]=false; } if(z+1<=q) if(!vis[x+3][y][z+1]) { vis[x+3][y][z+1]=true; dfs(x+3,y,z+1,1,step+1); vis[x+3][y][z+1]=false; } if(z-1>=1) if(!vis[x+3][y][z-1]) { vis[x+3][y][z-1]=true; dfs(x+3,y,z-1,4,step+1); vis[x+3][y][z-1]=false; } vis[x+1][y][z]=vis[x+2][y][z]=vis[x+3][y][z]=false; } if(x-2>=1) if(!vis[x][y][z]&&!vis[x-1][y][z]&&!vis[x-2][y][z]) { vis[x][y][z]=vis[x-1][y][z]=vis[x-2][y][z]=true; if(y+1<=m) if(!vis[x-2][y+1][z]) { vis[x-2][y+1][z]=true; dfs(x-2,y+1,z,5,step+1); vis[x-2][y+1][z]=false; } if(y-1>=1) if(!vis[x-2][y-1][z]) { vis[x-2][y-1][z]=true; dfs(x-2,y-1,z,2,step+1); vis[x-2][y-1][z]=false; } if(z+1<=q) if(!vis[x-2][y][z+1]) { vis[x-2][y][z+1]=true; dfs(x-2,y,z+1,1,step+1); vis[x-2][y][z+1]=false; } if(z-1>=1) if(!vis[x-2][y][z-1]) { vis[x-2][y][z-1]=true; dfs(x-2,y,z-1,4,step+1); vis[x-2][y][z-1]=false; } vis[x][y][z]=vis[x-1][y][z]=vis[x-2][y][z]=false; } } if(d==4) { if(z+1<=q) if(!vis[x][y][z]&&!vis[x][y][z+1]) { vis[x][y][z]=vis[x][y][z+1]=true; if(y+2<=m) if(!vis[x][y+1][z+1]&&!vis[x][y+2][z+1]) { vis[x][y+1][z+1]=vis[x][y+2][z+1]=true; dfs(x,y+2,z+1,5,step+1); vis[x][y+1][z+1]=vis[x][y+2][z+1]=false; } if(y-2>=1) if(!vis[x][y-1][z+1]&&!vis[x][y-2][z+1]) { vis[x][y-1][z+1]=vis[x][y-2][z+1]=true; dfs(x,y-2,z+1,2,step+1); vis[x][y-1][z+1]=vis[x][y-2][z+1]=false; } if(x+2<=n) if(!vis[x+1][y][z+1]&&!vis[x+2][y][z+1]) { vis[x+1][y][z+1]=vis[x+2][y][z+1]=true; dfs(x+2,y,z+1,3,step+1); vis[x+1][y][z+1]=vis[x+2][y][z+1]=false; } if(x-2>=1) if(!vis[x-1][y][z+1]&&!vis[x-2][y][z+1]) { vis[x-1][y][z+1]=vis[x-2][y][z+1]=true; dfs(x-2,y,z+1,6,step+1); vis[x-1][y][z+1]=vis[x-2][y][z+1]=false; } vis[x][y][z]=vis[x][y][z+1]=false; } if(z-2>=1) if(!vis[x][y][z-2]&&!vis[x][y][z-1]) { vis[x][y][z-1]=vis[x][y][z-2]=true; if(y+2<=m) if(!vis[x][y+1][z-2]&&!vis[x][y+2][z-2]) { vis[x][y+1][z-2]=vis[x][y+2][z-2]=true; dfs(x,y+2,z-2,5,step+1); vis[x][y+1][z-2]=vis[x][y+2][z-2]=false; } if(y-2>=1) if(!vis[x][y-1][z-2]&&!vis[x][y-2][z-2]) { vis[x][y-1][z-2]=vis[x][y-2][z-2]=true; dfs(x,y-2,z-2,2,step+1); vis[x][y-1][z-2]=vis[x][y-2][z-2]=false; } if(x+2<=n) if(!vis[x+1][y][z-2]&&!vis[x+2][y][z-2]) { vis[x+1][y][z-2]=vis[x+2][y][z-2]=true; dfs(x+2,y,z-2,3,step+1); vis[x+1][y][z-2]=vis[x+2][y][z-2]=false; } if(x-2>=1) if(!vis[x-1][y][z-2]&&!vis[x-2][y][z-2]) { vis[x-1][y][z-2]=vis[x-2][y][z-2]=true; dfs(x-2,y,z-2,6,step+1); vis[x-1][y][z-2]=vis[x-2][y][z-2]=false; } vis[x][y][z-1]=vis[x][y][z-2]=false; } if(z+2<=q) if(!vis[x][y][z]&&!vis[x][y][z+1]&&!vis[x][y][z+2]) { vis[x][y][z+1]=vis[x][y][z]=vis[x][y][z+2]=true; if(y+1<=m) if(!vis[x][y+1][z+2]) { vis[x][y+1][z+2]=true; dfs(x,y+1,z+2,5,step+1); vis[x][y+1][z+2]=false; } if(y-1<=m) if(!vis[x][y-1][z+2]) { vis[x][y-1][z+2]=true; dfs(x,y-1,z+2,2,step+1); vis[x][y-1][z+2]=false; } if(x+1<=m) if(!vis[x+1][y][z+2]) { vis[x+1][y][z+2]=true; dfs(x+1,y,z+2,3,step+1); vis[x+1][y][z+2]=false; } if(x-1<=m) if(!vis[x-1][y][z+2]) { vis[x-1][y][z+2]=true; dfs(x-1,y,z+2,6,step+1); vis[x-1][y][z+2]=false; } vis[x][y][z+1]=vis[x][y][z+2]=vis[x][y][z]=false; } if(z-3>=1) if(!vis[x][y][z-1]&&!vis[x][y][z-2]&&!vis[x][y][z-3]) { vis[x][y][z-1]=vis[x][y][z-2]=vis[x][y][z-3]=true; if(y+1<=m) if(!vis[x][y+1][z-3]) { vis[x][y+1][z-3]=true; dfs(x,y+1,z-3,5,step+1); vis[x][y+1][z-3]=false; } if(y-1<=m) if(!vis[x][y-1][z-3]) { vis[x][y-1][z-3]=true; dfs(x,y-1,z-3,2,step+1); vis[x][y-1][z-3]=false; } if(x+1<=m) if(!vis[x+1][y][z-3]) { vis[x+1][y][z-3]=true; dfs(x+1,y,z-2,3,step+1); vis[x+1][y][z-3]=false; } if(x-1<=m) if(!vis[x-1][y][z-3]) { vis[x-1][y][z-3]=true; dfs(x-1,y,z-3,6,step+1); vis[x-1][y][z-3]=false; } vis[x][y][z-3]=vis[x][y][z-2]=vis[x][y][z-1]=false; } } if(d==5) { if(y+2<=m) if(!vis[x][y+1][z]&&!vis[x][y+2][z]) { vis[x][y+1][z]=vis[x][y+2][z]=true; if(z+2<=q) if(!vis[x][y+2][z+2]&&!vis[x][y+2][z+1]) { vis[x][y+2][z+2]=vis[x][y+2][z+1]=true; dfs(x,y+2,z+2,1,step+1); vis[x][y+2][z+2]=vis[x][y+2][z+1]=false; } if(z-2>=1) if(!vis[x][y+2][z-1]&&!vis[x][y+2][z-2]) { vis[x][y+2][z-1]=vis[x][y+2][z-2]=true; dfs(x,y+2,z-2,4,step+1); vis[x][y+2][z-1]=vis[x][y+2][z-2]=false; } if(x+2<=n) if(!vis[x+1][y+2][z]&&!vis[x+2][y+2][z]) { vis[x+1][y+2][z]=vis[x+2][y+2][z]=true; dfs(x+2,y+2,z,3,step+1); vis[x+1][y+2][z]=vis[x+2][y+2][z]=false; } if(x-2>=1) if(!vis[x-1][y+2][z]&&!vis[x-2][y+2][z]) { vis[x-1][y+2][z]=vis[x-2][y+2][z]=true; dfs(x-2,y+2,z,6,step+1); vis[x-1][y+2][z]=vis[x-2][y+2][z]=false; } vis[x][y+1][z]=vis[x][y+2][z]=false; } if(y-1>=1) if(!vis[x][y][z]&&!vis[x][y-1][z]) { vis[x][y-1][z]=vis[x][y][z]=true; if(z+2<=q) if(!vis[x][y-1][z+1]&&!vis[x][y-1][z+2]) { vis[x][y-1][z+1]=vis[x][y-1][z+2]=true; dfs(x,y-1,z+2,1,step+1); vis[x][y-1][z+1]=vis[x][y-1][z+2]=false; } if(z-2>=1) if(!vis[x][y-1][z-1]&&!vis[x][y-1][z-2]) { vis[x][y-1][z-1]=vis[x][y-1][z-2]=true; dfs(x,y-1,z-2,4,step+1); vis[x][y-1][z-1]=vis[x][y-1][z-2]=false; } if(x+2<=n) if(!vis[x+1][y-1][z]&&!vis[x+2][y-1][z]) { vis[x+1][y-1][z]=vis[x+2][y-1][z]=true; dfs(x+2,y-1,z,3,step+1); vis[x+1][y-1][z]=vis[x+2][y-1][z]=false; } if(x-2>=1) if(!vis[x-1][y-1][z]&&!vis[x-2][y-1][z]) { vis[x-1][y-1][z]=vis[x-2][y-1][z]=true; dfs(x-2,y-1,z,6,step+1); vis[x-1][y-1][z]=vis[x-2][y-1][z]=false; } vis[x][y][z]=vis[x][y-1][z]=false; } if(y+3<=m) if(!vis[x][y+1][z]&&!vis[x][y+2][z]&&!vis[x][y+3][z]) { vis[x][y+1][z]=vis[x][y+2][z]=vis[x][y+3][z]=true; if(z+1<=q) if(!vis[x][y+3][z+1]) { vis[x][y+3][z+1]=true; dfs(x,y+3,z+1,1,step+1); vis[x][y+3][z+1]=false; } if(z-1>=1) if(!vis[x][y+3][z-1]) { vis[x][y+3][z-1]=true; dfs(x,y+3,z-1,4,step+1); vis[x][y+3][z-1]=false; } if(x+1<=n) if(!vis[x+1][y+3][z]) { vis[x+1][y+3][z]=true; dfs(x+1,y+3,z,3,step+1); vis[x+1][y+3][z]=false; } if(x-1>=1) if(!vis[x-1][y+3][z]) { vis[x-1][y+3][z]=true; dfs(x-1,y+3,z,6,step+1); vis[x-1][y+3][z]=false; } vis[x][y+3][z]=vis[x][y+1][z]=vis[x][y+2][z]=false; } if(y-2>=1) if(!vis[x][y-1][z]&&!vis[x][y-2][z]&&!vis[x][y][z]) { vis[x][y-1][z]=vis[x][y-2][z]=vis[x][y][z]=true; if(z+1<=q) if(!vis[x][y-2][z+1]) { vis[x][y-2][z+1]=true; dfs(x,y-2,z+1,1,step+1); vis[x][y-2][z+1]=false; } if(z-1>=1) if(!vis[x][y-2][z-1]) { vis[x][y-2][z-1]=true; dfs(x,y-2,z-1,4,step+1); vis[x][y-2][z-1]=false; } if(x+1<=n) if(!vis[x+1][y-2][z]) { vis[x+1][y-2][z]=true; dfs(x+1,y-2,z,3,step+1); vis[x+1][y-2][z]=false; } if(x-1>=1) if(!vis[x-1][y-2][z]) { vis[x-1][y-2][z]=true; dfs(x-1,y-2,z,6,step+1); vis[x-1][y-2][z]=false; } vis[x][y-1][z]=vis[x][y-2][z]=vis[x][y][z]=false; } } if(d==6) { if(x+1<=n) if(!vis[x][y][z]&&!vis[x+1][y][z]) { vis[x][y][z]=vis[x+1][y][z]=true; if(z+2<=q) if(!vis[x+1][y][z+1]&&!vis[x+1][y][z+2]) { vis[x+1][y][z+1]=vis[x+1][y][z+2]=true; dfs(x+1,y,z+2,1,step+1); vis[x+1][y][z+1]=vis[x+1][y][z+2]=false; } if(z-2>=1) if(!vis[x+1][y][z-1]&&!vis[x+1][y][z-2]) { vis[x+1][y][z-1]=vis[x+1][y][z-2]=true; dfs(x+1,y,z-2,4,step+1); vis[x+1][y][z-1]=vis[x+1][y][z-2]=false; } if(y+2<=m) if(!vis[x+1][y+1][z]&&!vis[x+1][y+2][z]) { vis[x+1][y+1][z]=vis[x+1][y+2][z]=true; dfs(x+1,y+2,z,5,step+1); vis[x+1][y+1][z]=vis[x+1][y+2][z]=false; } if(y-2>=1) if(!vis[x+1][y-1][z]&&!vis[x+1][y-2][z]) { vis[x+1][y-1][z]=vis[x+1][y-2][z]=true; dfs(x+1,y-2,z,2,step+1); vis[x+1][y-1][z]=vis[x+1][y-2][z]=false; } vis[x+1][y][z]=vis[x][y][z]=false; } if(x-2>=1) if(!vis[x-1][y][z]&&!vis[x-2][y][z]) { vis[x-1][y][z]=vis[x-2][y][z]=true; if(z+2<=q) if(!vis[x-2][y][z+1]&&!vis[x-2][y][z+2]) { vis[x-2][y][z+1]=vis[x-2][y][z+2]=true; dfs(x-2,y,z+2,1,step+1); vis[x-2][y][z+1]=vis[x-2][y][z+2]=false; } if(z-2>=1) if(!vis[x-2][y][z-1]&&!vis[x-2][y][z-2]) { vis[x-2][y][z-1]=vis[x-2][y][z-2]=true; dfs(x-2,y,z-2,4,step+1); vis[x-2][y][z-1]=vis[x-2][y][z-2]=false; } if(y+2<=m) if(!vis[x-2][y+1][z]&&!vis[x-2][y+2][z]) { vis[x-2][y+1][z]=vis[x-2][y+2][z]=true; dfs(x-2,y+2,z,5,step+1); vis[x-2][y+1][z]=vis[x-2][y+2][z]=false; } if(y-2>=1) if(!vis[x-2][y-1][z]&&!vis[x-2][y-2][z]) { vis[x-2][y-1][z]=vis[x-2][y-2][z]=true; dfs(x-2,y-2,z,2,step+1); vis[x-2][y-1][z]=vis[x-2][y-2][z]=false; } vis[x-2][y][z]=vis[x-1][y][z]=false; } if(x+2<=n) if(!vis[x+1][y][z]&&!vis[x+2][y][z]&&!vis[x][y][z]) { vis[x+1][y][z]=vis[x+2][y][z]=vis[x][y][z]=true; if(y+1<=m) if(!vis[x+2][y+1][z]) { vis[x+2][y+1][z]=true; dfs(x+2,y+1,z,5,step+1); vis[x+2][y+1][z]=false; } if(y-1>=1) if(!vis[x+2][y-1][z]) { vis[x+2][y-1][z]=true; dfs(x+2,y-1,z,2,step+1); vis[x+2][y-1][z]=false; } if(z+1<=q) if(!vis[x+2][y][z+1]) { vis[x+2][y][z+1]=true; dfs(x+2,y,z+1,1,step+1); vis[x+2][y][z+1]=false; } if(z-1>=1) if(!vis[x+2][y][z-1]) { vis[x+2][y][z-1]=true; dfs(x+2,y,z-1,4,step+1); vis[x+2][y][z-1]=false; } vis[x+1][y][z]=vis[x+2][y][z]=vis[x][y][z]=false; } if(x-3>=1) if(!vis[x-3][y][z]&&!vis[x-1][y][z]&&!vis[x-2][y][z]) { vis[x-3][y][z]=vis[x-1][y][z]=vis[x-2][y][z]=true; if(y+1<=m) if(!vis[x-3][y+1][z]) { vis[x-3][y+1][z]=true; dfs(x-3,y+1,z,5,step+1); vis[x-3][y+1][z]=false; } if(y-1>=1) if(!vis[x-3][y-1][z]) { vis[x-3][y-1][z]=true; dfs(x-3,y-1,z,2,step+1); vis[x-3][y-1][z]=false; } if(z+1<=q) if(!vis[x-3][y][z+1]) { vis[x-3][y][z+1]=true; dfs(x-3,y,z+1,1,step+1); vis[x-3][y][z+1]=false; } if(z-1>=1) if(!vis[x-3][y][z-1]) { vis[x-3][y][z-1]=true; dfs(x-3,y,z-1,4,step+1); vis[x-3][y][z-1]=false; } vis[x-3][y][z]=vis[x-1][y][z]=vis[x-2][y][z]=false; } } } int main() { freopen("blessyou.in","r",stdin); freopen("blessyou.out","w",stdout); in(n),in(m),in(q),in(p); char op[4]; in(sx),in(sy),in(sz),scanf("%s",op); if(op[0]=='x') if(sx==1) sd=6; else sd=3; else if(op[0]=='y') if(sy==1) sd=2; else sd=5; else if(sz==1) sd=4; else sd=1; in(ex),in(ey),in(ez),scanf("%s",op); if(op[0]=='x') if(ex==1) ed=6; else ed=3; else if(op[0]=='y') if(ey==1) ed=2; else ed=5; else if(ez==1) ed=4; else ed=1; int tmpx,tmpy,tmpz; for(int i=1;i<=p;i++) { in(tmpx),in(tmpy),in(tmpz); vis[tmpx][tmpy][tmpz]=true; } ans=13; dfs(sx,sy,sz,sd,0); if(ans==13) cout<<"Dream Battle"; else cout<<ans; return 0; }
#include <cstdio> int main (int argc, char *argv[]) { freopen ("count.in", "r", stdin); freopen ("count.out", "w", stdout); int N; scanf ("%d", &N); int Answer = N; register int i, j; for (i = 2; i <= N; ++ i) for (j = i; j <= N; j += i) ++ Answer; printf ("%d", Answer); fclose (stdin); fclose (stdout); return 0; }
#include <cstdio> #include <iostream> #define rg register #define INF 2e9 inline void read (int &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } #define Max 400 int c[Max], s[Max][Max], f[Max][Max]; inline void cmin (int &a, int b) { if (b < a) a = b; } int main (int argc, char *argv[]) { freopen ("post.in", "r", stdin); freopen ("post.out", "w", stdout); int N, M; read (N), read (M); rg int i, j, k; for (i = 1; i <= N; ++ i) read (c[i]); for (i = 1; i <= N; ++ i) for (j = i + 1; j <= N; ++ j) s[i][j] = s[i][j - 1] + c[j] - c[(i + j) >> 1]; for (i = 1; i <= N; ++ i) f[i][1] = s[1][i]; for (i = 1; i <= N; ++ i) for (j = 2; j <= M; ++ j) for (k = 1, f[i][j] = INF; k < i; ++ k) cmin (f[i][j], f[k][j - 1] + s[k + 1][i]); printf ("%d", f[N][M]); fclose (stdin); fclose (stdout); return 0; }
#include <cstdio> #include <cstring> #include <iostream> #include <map> #define rg register #define Max 10001 const int Mod = 15; struct Int { int len, data[Max]; void clear() { memset(this, 0, sizeof(*this)); } int &operator [] (int k) { return data[k]; } Int &operator = (int k) { clear(), len = 0; for (; k; k >>= 4) { ++ len, data[len] = k & Mod; } if (len == 0) ++len; return *this; } Int operator * (Int & A) { Int temp; temp.clear (); temp.len = len + A.len - 1; rg int i, j; for (i = 1; i <= len; ++ i) for (j = 1; j <= A.len; ++ j) { temp[i + j - 1] += A[j] * data[i]; temp[i + j] += (temp[i + j - 1] >> 4); temp[i + j - 1] &= Mod; } for (; temp[temp.len + 1]; ++ temp.len); return temp; } void print() { for (rg int i = len; i >= 1; i--) printf("%X", data[i]); putchar(' '); } } temp, Answer; std :: map <int, bool> M; bool f[Max * 100]; int pnum, p[Max * 10]; void Prepare(int M) { memset(f, 1, sizeof(f)); f[0] = f[1] = false; p[pnum = 1] = 2; rg int now, j; for (now = 2; now < M;) { for (j = now + now; j <= M; f[j] = false, j += now); for (++ now; now < M && !f[now]; ++ now); if (f[now]) p[++pnum] = now; } } inline void read (int &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } int Gcd(int a, int b) { return !b ? a : Gcd(b, a % b); } void work(int num) { for (rg int i = 1; i <= pnum; i++) { if (num % p[i] == 0) if (M[p[i]] == 0) M[p[i]] = true, temp = p[i], Answer = Answer * temp; for (; num % p[i] == 0; num /= p[i]); } if (num != 1) if (M[num] == 0) M[num] = true, temp = num, Answer = Answer * temp; } int main (int argc, char *argv[]) { freopen ("fraction.in", "r", stdin); freopen ("fraction.out", "w", stdout); Answer = 1; int t, a, b, d; read (t); Prepare (100000); for (; t; -- t) read (a), read (b), d = Gcd(a, b), a /= d, b /= d, work(b); Answer.print(); fclose (stdin); fclose (stdout); return 0; }
#include <cstdio> #include <iostream> #include <queue> #include <cstring> std :: string Name = "fireworks", _I = ".in", _O = ".out"; #define rg register #define flo double inline void read (int &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } #define Max 201009 struct E { E *n; int v, d; } *list[Max], poor[Max << 1], *Ta = poor; int in[Max], dis[Max], N, M; bool is[Max]; void Spfa () { std :: queue <int> Q; E * e; rg int i, n, v; memset (dis, 127/3, sizeof dis); for (i = 1; i <= N; ++ i) if (in[i] == 1) Q.push (i), is[i] = true, dis[i] = 0; for (; !Q.empty (); Q.pop ()) for (n = Q.front (), is[n] = false, e = list[n]; e; e = e->n) if (dis[v = e->v] > dis[n] + e->d) { dis[v] = dis[n] + e->d; if (!is[v]) is[v] = true, Q.push (v); } } inline void In (int x, int y, int z) { ++ Ta, Ta->v = y, Ta->n = list[x], list[x] = Ta, Ta->d = z, ++ in[y]; } inline void cmax (flo &x, flo y) { if (y > x) x = y; } int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); rg int i; flo s; int x, y, z; E *e; read (M), N = M + 1; for (i = 1; i <= M; ++ i) read (x), read (y), read (z), In (x, y, z), In (y, x, z); for (Spfa (), i = 1; i <= N; ++ i) for (e = list[i]; e; e = e->n) cmax (s, (dis[i] + dis[e->v] + e->d) / 2.0); printf ("%0.1lf", s); return 0; }
#include <cstdio> #include <iostream> std :: string Name = "stone", _I = ".in", _O = ".out"; #define rg register inline void read (int &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } #define Max 120 #define INF 1e9 inline void cmax (int &a, int b) { if (b > a) a = b; } int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); int N, M, Mn, Mx, x, p; read (N), read (M); rg int i, j, k; static int h[Max], s = 0; for (i = 1; i <= N; ++ i) { for (j = 1, read (x), Mn = INF; j <= M - x + 1; ++ j) { for (k = 1, Mx = 0; k <= x; ++ k) cmax (Mx, h[j + k - 1]); if (Mx < Mn) Mn = Mx, p = j; } for (j = 1; j <= x; ++ j) h[p + j - 1] = Mn + x; } for (i = 1; i <= N; ++ i) cmax (s, h[i]); printf ("%d", s); return 0; }
#include <cstdio> #include <cstring> #include <iostream> #define rg register #define Max 1000005 #define INF 1e9 std :: string Name = "piano", _I = ".in", _O = ".out"; int N, M, a[Max], f[Max], maxn[Max]; inline void read (int &n) { rg char c = getchar (); bool temp = false; for (n = 0; !isdigit (c); c = getchar ()) if (c == '-') temp = true; for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); if (temp) n = -n; } inline int max (int a, int b) { return a > b ? a : b; } inline int cmax (int &a, int b) { if (b > a) a = b; } int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); for (; scanf ("%d%d", &M, &N) != EOF; ) { rg int i, j; int s = 0; memset (f, 0, sizeof f); memset (maxn, 0, sizeof maxn); for (i = 1; i <= N; ++ i) read (a[i]); for (j = 1; j <= M; ++ j) for (i = j, s = -INF; i <= N; ++ i) f[i] = max (f[i - 1], maxn[i - 1]) + a[i], maxn[i-1]=s, cmax (s, f[i]); printf ("%d ",s); } return 0; }
/* T1 对原矩阵做一遍模k意义下的二维前缀和 求多少子矩阵的和是K的倍数 易知若两个子矩阵和模K的余数相同，那么任取两个相减必定是k的倍数 那么统计一下前缀和中模k相同的数的对数即可 */ #include <cstdio> #include <iostream> std :: string Name = "rally", _I = ".in", _O = ".out"; #define rg register inline void read (int &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } #define Max 410 typedef long long LL; LL s[Max][Max]; LL _s; int c[1000006], b[1000006]; int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); int N, M, K, z; read (N), read (M), read (K); rg int i, j, k; for (i = 1; i <= N; ++ i) for (j = 1; j <= M; ++ j) read (z), s[i][j] = (s[i - 1][j] + s[i][j - 1] + z + K - s[i - 1][j - 1]) % K; for (i = 1; i <= N; ++ i) for (j = i; j <= N; ++ j) { for (k = 1, c[0] = 1; k <= M; ++ k) _s += c[(b[k] = s[j][k] + K - s[i - 1][k]) %= K] ++; for (k = 1; k <= M; ++ k) c[b[k]] = 0; } std :: cout << _s; return 0; }
#include <iostream> #include <cstdio> #define rg register inline void read (int &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } #define Max 100005 int N, K, s; struct E { E *n; int v; } *list[Max], pool[Max << 1], *Ta = pool; inline void In (int u, int v) { ++ Ta, Ta->v = v, Ta->n = list[u], list[u] = Ta; } inline void cmin (int &a, int b) { if (b < a) a = b; } inline void cmax (int &a, int b) { if (b > a) a = b; } int Dfs (int n, int F) { int mx = -N, mn = N, p; bool f = false; rg E *e; int v; for (e = list[n]; e; e = e->n) if ((v = e->v) != F) f = true, p = Dfs (v, n), cmax (mx, p), cmin (mn, p); if (!f) return 1; else if (mx + mn < 0) return mn + 1; else if (mx >= K) { ++ s; return -K; } else if (n == 1 && mx >= 0) { ++ s; return -K; } else return mx + 1; } std :: string Name = "general", _I = ".in", _O = ".out"; int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); int T, x, y; read (N), read (K), read (T); rg int i; if (K == 0) return printf ("%d", N), 0; for (i = 1; i < N; ++ i) read (x), read (y), In (x, y), In (y, x); Dfs (1, 0); if (N <= 1) s = 1; printf ("%d", s); return 0; }
#include <cstring> #include <cstdio> #include <queue> #include <iostream> #define Max 40005 #define INF 1e8 namespace Z { void read (int &now) { now = 0; register char word = getchar (); while (word < '0' || word > '9') word = getchar (); while (word >= '0' && word <= '9') { now = now * 10 + word - '0'; word = getchar (); } } inline int min (const int &_Qos_swc, const int &_Cos_ses) { return _Qos_swc < _Cos_ses ? _Qos_swc : _Cos_ses; } } int S, T = 45; int M, N, K; int key[Max]; int size[Max], _r[Max]; int Answer; int Count; int date[Max]; int number[Max]; int cost[Max / 100][Max / 100]; bool visit[Max]; int dis[Max]; void Bfs (int res) { memset (visit, false, sizeof (visit)); std :: queue <int> Queue; visit[res] = true; dis[res] = 0; Queue.push (res); int now; while (!Queue.empty ()) { now = Queue.front (); Queue.pop (); for (int i = 1; i <= M; i++) { if (now + size[i] <= N && (!visit[size[i] + now])) { visit[size[i] + now] = true; dis[now + size[i]] = dis[now] + 1; Queue.push (now + size[i]); } if (now - size[i] >= 0 && (!visit[now - size[i]])) { visit[now - size[i]] = true; dis[now - size[i]] = dis[now] + 1; Queue.push (now - size[i]); } } } } class Net_Flow_Type { private : struct Edge_Date { int from; int to; int flow; int next; int cost; } edge[Max << 2]; int Edge_Count; int edge_list[Max]; int deep[Max]; int pre[Max]; public : void Prepare () { Edge_Count = 1; } inline void AddEdge (int from, int to, int flow, int cost) { Edge_Count++; edge[Edge_Count].from = from; edge[Edge_Count].to = to; edge[Edge_Count].flow = flow; edge[Edge_Count].cost = cost; edge[Edge_Count].next = edge_list[from]; edge_list[from] = Edge_Count; Edge_Count++; edge[Edge_Count].from = to; edge[Edge_Count].to = from; edge[Edge_Count].flow = 0; edge[Edge_Count].cost = -cost; edge[Edge_Count].next = edge_list[to]; edge_list[to] = Edge_Count; } bool Spfa () { for (int i = 0; i <= T; i++) deep[i] = INF; std :: queue <int> Queue; memset (visit, false, sizeof visit); Queue.push (S); deep[S] = 0; visit[S] = true; int now; while (!Queue.empty ()) { now = Queue.front (); Queue.pop (); for (int i = edge_list[now]; i; i = edge[i].next) if (edge[i].flow && deep[now] + edge[i].cost < deep[edge[i].to]) { deep[edge[i].to] = deep[now] + edge[i].cost; pre[edge[i].to] = i; if (!visit[edge[i].to]) { visit[edge[i].to] = true; Queue.push (edge[i].to); } } visit[now] = false; } return deep[T] < INF; } void Dinic () { while (Spfa ()) { int res = INF; for (int i = pre[T]; i; i = pre[edge[i].from]) res = Z :: min (res, edge[i].flow); for (int i = pre[T]; i; i = pre[edge[i].from]) { edge[i].flow -= res; edge[i ^ 1].flow += res; Answer += edge[i].cost * res; } } } void Insert_Edges () { for (int i = 1; i <= Count; i++) { AddEdge (S, i, 1, 0); AddEdge (i + Count, T, 1, 0); } for (int i = 1; i <= Count; i++) for (int j = 1; j <= Count; j++) if (i != j && cost[i][j] != INF) AddEdge (i, j + Count, 1, cost[i][j]); } }; Net_Flow_Type Make; std :: string Name = "starlit", _I = ".in", _O = ".out"; int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); Z :: read (N); Z :: read (K); Z :: read (M); Make.Prepare (); int x; for (int i = 1; i <= K; i++) Z :: read (x), date[x] = true; for (int i = 1; i <= M; i++) Z :: read (size[i]); for (int i = 0; i <= N; i++) if (date[i] != date[i + 1]) number[i] = ++Count; for (int i = 0; i <= N; i++) if (date[i] != date[i + 1]) { Bfs (i); for (int j = 0; j <= N; j++) { if (!number[j]) continue; if (!visit[j]) cost[number[i]][number[j]] = INF; else cost[number[i]][number[j]] = dis[j]; } } Make.Insert_Edges (); Make.Dinic (); printf ("%d", Answer >> 1); return 0; }
#include <iostream> #include <cstdio> #define rg register #define Max 30005 int f[Max], s[Max], d[Max]; #undef Max #define Max 30000 inline void read (int &n) { rg char c = getchar (); for (n = 0; !isdigit (c); c = getchar ()); for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } int Find (register int x) { for (; x != f[x]; x = f[x]) s[f[x]] = s[x] + 1; return x; } std :: string Name = "cube", _I = ".in", _O = ".out"; int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); int N, x, y, z; read (N); rg int i; char t[10]; for (i = 1; i <= Max; ++ i) f[i] = d[i] = i; for (; N; -- N) { scanf ("%s", t), read (x); if (t[0] == 'M') { read (y), z = d[y]; x = d[Find (x)], y = Find (y); f[y] = x; for (; x != f[x]; x = f[x]) d[x] = z; d[x] = z; Find (z); } else printf ("%d ", s[x]); } return 0; }
#include <cstdio> #include <iostream> #include <cstring> #define INF 1e8 #define Max 50010 char l[Max]; #define rg register int _n[Max], _l[Max], N, S; int rex[Max], rey[Max], rexn[Max], reyl[Max], t, T; int Erase (int i) { int res = 0; for (int x, c, cl, cr, n, y, r; i != 0 && i != T && (l[_l[i]] == l[i] || l[_n[i]] == l[i]); ) { c = l[i]; cl = cr = 0; for (x = i; l[x] == c; ++ cl, x = _l[x]); -- cl; for (y = i; l[y] == c; ++ cr, y = _n[y]); -- cr; if (cl + cr >= 2) { if (x == 0) S = y; rex[++ t] = x, rey[t] = y, rexn[t] = _n[x], reyl[t] = _l[y], i = x, _n[x] = y, _l[y] = x, res += cl + cr + 1; } else break; } return res; } int C, Answer = INF; void Dfs (int Len, int s) { if (s >= Answer) return ; if (Len <= 0) { Answer = s; return ; } int C0 = 0, C1 = 1, x, y, z, rs; rg int i; for (i = S; i != T; i = _n[i]) { if (l[i] == l[_n[i]]) { x = _n[_n[i]], y = _l[_n[_n[i]]]; rs = S; _n[_n[i]] = ++ C, _l[x] = C, l[C] = l[i]; _l[C] = _n[i], _n[C] = x; Dfs (Len - Erase (C), s + 1); S = rs; for (; t; -- t) _n[rex[t]] = rexn[t], _l[rey[t]] = reyl[t]; _n[_n[i]] = x, _l[_n[_n[i]]] = y; -- C; } } } std :: string Name = "zuma", _I = ".in", _O = ".out"; int main (int argc, char *argv[]) { freopen ((Name + _I).c_str (), "r", stdin); freopen ((Name + _O).c_str (), "w", stdout); scanf ("%s", l + 1); N = strlen (l + 1); rg int i, j; int C1 = 0, C0 = 0; for (i = 1; i <= N; ++ i) _l[i] = i - 1, _n[i] = i + 1; _n[N] = -1; S = 1, T = -1; C = N; Dfs (N, 0); printf ("%d", Answer); return 0; }