#pragma GCC optimize ("Ofast") #define _USE_MATH_DEFINES #include <bits/stdc++.h> #define FOR(i, a, b) for (auto i=(a); i<(b); i++) #define FORD(i, a, b) for (int i=(a); i>(b); i--) #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(), (x).end() #define PPC(x) __builtin_popcountll(x) #define MSB(x) (63 - __builtin_clzll(x)) #define LSB(x) __builtin_ctz(x) #define ARG(x, i) (get<i>(x)) #define ithBit(m, i) ((m) >> (i) & 1) #define pb push_back #define ft first #define sd second #define kw(a) ((a) * (a)) #ifdef DEBUG #include "debug.h" #else #define dbg(...) 0 #endif using namespace std; template <typename T1, typename T2> inline void remin(T1& a, T2 b) { a = min(a, (T1)b); } template <typename T1, typename T2> inline void remax(T1& a, T2 b) { a = max(a, (T1)b); } const int maxN = 1 << 18, maxM = 1'500'000; namespace FFM { int E[maxM][3]; vector <int> G[maxN]; int fet[maxN], vis[maxN], Q[maxN]; int m, visCtr, s, t; inline void conn(int a, int b) { E[m][0] = a, E[m][1] = b, E[m][2] = 0; G[a].pb(m), G[b].pb(m); m++; } void cutTarget() { for (int e : G[t]) G[E[e][0]].pop_back(); m -= SZ(G[t]); G[t].resize(0); } void push(int v) { E[G[v].back()][2] = 1; // t --> v while (v != s) { int e = fet[v]; v = E[e][ E[e][2] ]; E[e][2] ^= 1; } } void updt() { int bb = 0; #define INS(v, e) Q[bb++] = v, vis[v] = visCtr, fet[v] = e visCtr++; INS(s, -1); for (int ff = 0; ff != bb; ff++) { int v = Q[ff]; for (int e : G[v]) { int u = E[e][ E[e][2]^1 ]; if (vis[u] != visCtr) INS(u, e); } } } void clear() { cutTarget(); FOR(i, 0, m) E[i][2] = 0; } inline bool richable(int v) { return vis[v] == visCtr; } } int in[maxN], out[maxN]; long long res[maxN]; void solve() { int n, m, k, s = 0, src = s++; scanf ("%d%d%d", &n, &m, &k); FOR(i, 1, k+1) { in[i] = out[i] = s++; FFM::conn(src, in[i]); } FOR(i, k+1, n+1) { in[i] = s++, out[i] = s++; FFM::conn(in[i], out[i]); } while (m--) { int a, b; scanf ("%d%d", &a, &b); FFM::conn(out[a], in[b]); } int trg = s++; FFM::s = src, FFM::t = trg; FOR(l, k+1, n+1) { FFM::updt(); int flow = 0; FOR(r, l, n+1) { FFM::conn(out[r], trg); if (FFM::richable(out[r])) FFM::push(out[r]), FFM::updt(), flow++; res[flow]++; } FFM::clear(); } FOR(i, 0, k+1) printf("%lld\n", res[i]); } int main() { int t = 1; //scanf ("%d", &t); FOR(tid, 1, t+1) { //printf("Case #%d: ", tid); solve(); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 | #pragma GCC optimize ("Ofast") #define _USE_MATH_DEFINES #include <bits/stdc++.h> #define FOR(i, a, b) for (auto i=(a); i<(b); i++) #define FORD(i, a, b) for (int i=(a); i>(b); i--) #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(), (x).end() #define PPC(x) __builtin_popcountll(x) #define MSB(x) (63 - __builtin_clzll(x)) #define LSB(x) __builtin_ctz(x) #define ARG(x, i) (get<i>(x)) #define ithBit(m, i) ((m) >> (i) & 1) #define pb push_back #define ft first #define sd second #define kw(a) ((a) * (a)) #ifdef DEBUG #include "debug.h" #else #define dbg(...) 0 #endif using namespace std; template <typename T1, typename T2> inline void remin(T1& a, T2 b) { a = min(a, (T1)b); } template <typename T1, typename T2> inline void remax(T1& a, T2 b) { a = max(a, (T1)b); } const int maxN = 1 << 18, maxM = 1'500'000; namespace FFM { int E[maxM][3]; vector <int> G[maxN]; int fet[maxN], vis[maxN], Q[maxN]; int m, visCtr, s, t; inline void conn(int a, int b) { E[m][0] = a, E[m][1] = b, E[m][2] = 0; G[a].pb(m), G[b].pb(m); m++; } void cutTarget() { for (int e : G[t]) G[E[e][0]].pop_back(); m -= SZ(G[t]); G[t].resize(0); } void push(int v) { E[G[v].back()][2] = 1; // t --> v while (v != s) { int e = fet[v]; v = E[e][ E[e][2] ]; E[e][2] ^= 1; } } void updt() { int bb = 0; #define INS(v, e) Q[bb++] = v, vis[v] = visCtr, fet[v] = e visCtr++; INS(s, -1); for (int ff = 0; ff != bb; ff++) { int v = Q[ff]; for (int e : G[v]) { int u = E[e][ E[e][2]^1 ]; if (vis[u] != visCtr) INS(u, e); } } } void clear() { cutTarget(); FOR(i, 0, m) E[i][2] = 0; } inline bool richable(int v) { return vis[v] == visCtr; } } int in[maxN], out[maxN]; long long res[maxN]; void solve() { int n, m, k, s = 0, src = s++; scanf ("%d%d%d", &n, &m, &k); FOR(i, 1, k+1) { in[i] = out[i] = s++; FFM::conn(src, in[i]); } FOR(i, k+1, n+1) { in[i] = s++, out[i] = s++; FFM::conn(in[i], out[i]); } while (m--) { int a, b; scanf ("%d%d", &a, &b); FFM::conn(out[a], in[b]); } int trg = s++; FFM::s = src, FFM::t = trg; FOR(l, k+1, n+1) { FFM::updt(); int flow = 0; FOR(r, l, n+1) { FFM::conn(out[r], trg); if (FFM::richable(out[r])) FFM::push(out[r]), FFM::updt(), flow++; res[flow]++; } FFM::clear(); } FOR(i, 0, k+1) printf("%lld\n", res[i]); } int main() { int t = 1; //scanf ("%d", &t); FOR(tid, 1, t+1) { //printf("Case #%d: ", tid); solve(); } return 0; } |