結果
問題 | No.2403 "Eight" Bridges of Königsberg |
ユーザー | hudson |
提出日時 | 2023-08-05 16:58:12 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 37,843 bytes |
コンパイル時間 | 3,531 ms |
コンパイル使用メモリ | 230,384 KB |
実行使用メモリ | 19,092 KB |
最終ジャッジ日時 | 2024-10-15 14:02:17 |
合計ジャッジ時間 | 6,441 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 44 ms
5,248 KB |
testcase_05 | AC | 87 ms
5,248 KB |
testcase_06 | AC | 93 ms
5,248 KB |
testcase_07 | AC | 55 ms
5,248 KB |
testcase_08 | AC | 65 ms
5,248 KB |
testcase_09 | AC | 99 ms
5,248 KB |
testcase_10 | AC | 94 ms
5,248 KB |
testcase_11 | AC | 72 ms
5,248 KB |
testcase_12 | AC | 98 ms
5,248 KB |
testcase_13 | AC | 67 ms
5,248 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long #define ALL(a) (a).begin(),(a.end()) #define brep(n,hhh) for(int i=n-1;i>=hhh;i--) #define rep(hhh,n) for(int i=hhh;i<n;i++) #define jrep(hhh,n) for(int j=hhh;j<n;j++) #define krep(hhh,n) for(int k=hhh;k<n;k++) #define lrep(hhh,n) for(int l=hhh;l<n;l++) #define rrep(i,k,n) for(int i=k;i<n;i++) #define out(n) cout << n <<endl; #define sot(A) sort(A.begin(),A.end()) #define rsot(A) sort(A.rbegin(),A.rend()) #define vi vector<int> #define vb vector<bool> #define vd vector<double> #define vld vector<long double> #define vpd vector<pair<double,double>> #define vc vector<char> #define vs vector<string> #define vpi vector<pair<int,int>> #define vvc vector<vector<char>> #define vvi vector<vector<int>> #define vvd vector<vector<double>> #define vvpd vector<vector<pair<double,double>>> #define vvb vector<vector<bool>> #define vvvi vector<vector<vector<int>>> #define vvvvi vector<vector<vector<vector<int>>>> #define vvvpi vector<vector<vector<Pi>>> #define vvpi vector<vector<pair<int,int>>> #define vvtpi vector<vector<tuple<int,int,int>>> #define dout(x,y) cout<<x<<" "<<y<<endl; #define tout(x,y,z) cout<<x<<" "<<y<<" "<<z<<endl; #define Pi pair<int,int> #define Pd pair<double,double> #define Pdi pair<double,int> #define TPi tuple<int,int,int> #define QPi tuple<int,int,int,int> #define FPi tuple<int,int,int,int,int> #define TPd tuple<double,int,int> #define spi pair<string,int> #define pb push_back constexpr int MOD1=1000000007; constexpr int MOD2=998244353; constexpr int BIG=10000000000000000; //int BBB=ppow(2,31)-1; class BIT { public: //データの長さ int n; //データの格納先 vector<int> a; //コンストラクタ BIT(int n):n(n),a(n+1,0){} //a[i]にxを加算する void add(int i,int x){ i++; if(i==0) return; for(int k=i;k<=n;k+=(k & -k)){ a[k]+=x; //a[k]%=MOD2; } } void conf(){ for(int i=0;i<=n;i++){ cout<<a[i]<<' '; } cout<<endl; } //a[i]+a[i+1]+…+a[j]を求める int sum(int i,int j){ return (sum(j)-sum(i-1)); } //a[0]+a[1]+…+a[i]を求める int sum(int i){ i++; int s=0; if(i==0) return s; for(int k=i;k>0;k-=(k & -k)){ s+=a[k]; //s%=MOD2; } return s; } //a[0]+a[1]+…+a[i]>=xとなる最小のiを求める(任意のkでa[k]>=0が必要) int lower_bound(int x){ if(x<=0){ //xが0以下の場合は該当するものなし→0を返す return 0; }else{ int i=0;int r=1; //最大としてありうる区間の長さを取得する //n以下の最小の二乗のべき(BITで管理する数列の区間で最大のもの)を求める while(r<n) r=r<<1; //区間の長さは調べるごとに半分になる for(int len=r;len>0;len=len>>1) { //その区間を採用する場合 if(i+len<n && a[i+len]<x){ x-=a[i+len]; i+=len; } } return i; } } }; class CR{ public: vi fac; vi finv; vi inv; int MOD; CR(int N,int M):fac(N+1),finv(N+1),inv(N+1){ MOD=M; fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i <= N; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } // 二項係数計算 long long COM(int n, int k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } };//MODには素数 namespace internal { template <class T> struct simple_queue { std::vector<T> payload; int pos = 0; void reserve(int n) { payload.reserve(n); } int size() const { return (int)(payload.size()) - pos; } bool empty() const { return pos == (int)(payload.size()); } void push(const T& t) { payload.push_back(t); } T& front() { return payload[pos]; } void clear() { payload.clear(); pos = 0; } void pop() { pos++; } }; } template <class Cap> struct mf_graph { public: mf_graph() : _n(0) {} mf_graph(int n) : _n(n), g(n) {} int add_edge(int from, int to, Cap cap) { assert(0 <= from && from < _n); assert(0 <= to && to < _n); assert(0 <= cap); int m = (int)(pos.size()); pos.push_back({from, (int)(g[from].size())}); int from_id = (int)(g[from].size()); int to_id = (int)(g[to].size()); if (from == to) to_id++; g[from].push_back(_edge{to, to_id, cap}); g[to].push_back(_edge{from, from_id, 0}); return m; } struct edge { int from, to; Cap cap, flow; }; edge get_edge(int i) { int m = (int)(pos.size()); assert(0 <= i && i < m); auto _e = g[pos[i].first][pos[i].second]; auto _re = g[_e.to][_e.rev]; return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap}; } std::vector<edge> edges() { int m = (int)(pos.size()); std::vector<edge> result; for (int i = 0; i < m; i++) { result.push_back(get_edge(i)); } return result; } void change_edge(int i, Cap new_cap, Cap new_flow) { int m = (int)(pos.size()); assert(0 <= i && i < m); assert(0 <= new_flow && new_flow <= new_cap); auto& _e = g[pos[i].first][pos[i].second]; auto& _re = g[_e.to][_e.rev]; _e.cap = new_cap - new_flow; _re.cap = new_flow; } Cap flow(int s, int t) { return flow(s, t, std::numeric_limits<Cap>::max()); } Cap flow(int s, int t, Cap flow_limit) { assert(0 <= s && s < _n); assert(0 <= t && t < _n); assert(s != t); std::vector<int> level(_n), iter(_n); internal::simple_queue<int> que; auto bfs = [&]() { std::fill(level.begin(), level.end(), -1); level[s] = 0; que.clear(); que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (auto e : g[v]) { if (e.cap == 0 || level[e.to] >= 0) continue; level[e.to] = level[v] + 1; if (e.to == t) return; que.push(e.to); } } }; auto dfs = [&](auto self, int v, Cap up) { if (v == s) return up; Cap res = 0; int level_v = level[v]; for (int& i = iter[v]; i < (int)(g[v].size()); i++) { _edge& e = g[v][i]; if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue; Cap d = self(self, e.to, std::min(up - res, g[e.to][e.rev].cap)); if (d <= 0) continue; g[v][i].cap += d; g[e.to][e.rev].cap -= d; res += d; if (res == up) break; } return res; }; Cap flow = 0; while (flow < flow_limit) { bfs(); if (level[t] == -1) break; std::fill(iter.begin(), iter.end(), 0); while (flow < flow_limit) { Cap f = dfs(dfs, t, flow_limit - flow); if (!f) break; flow += f; } } return flow; } std::vector<bool> min_cut(int s) { std::vector<bool> visited(_n); internal::simple_queue<int> que; que.push(s); while (!que.empty()) { int p = que.front(); que.pop(); visited[p] = true; for (auto e : g[p]) { if (e.cap && !visited[e.to]) { visited[e.to] = true; que.push(e.to); } } } return visited; } private: int _n; struct _edge { int to, rev; Cap cap; }; std::vector<std::pair<int, int>> pos; std::vector<std::vector<_edge>> g; }; int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()> struct lazy_segtree { public: lazy_segtree() : lazy_segtree(0) {} lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {} lazy_segtree(const std::vector<S>& v) : _n((int)v.size()) { log = ceil_pow2(_n); size = 1 << log; d = std::vector<S>(2 * size, e()); lz = std::vector<F>(size, id()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); if (l == r) return e(); l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push(r >> i); } S sml = e(), smr = e(); while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } void apply(int p, F f) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = mapping(f, d[p]); for (int i = 1; i <= log; i++) update(p >> i); } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= _n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { int l2 = l, r2 = r; while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; } for (int i = 1; i <= log; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template <bool (*g)(S)> int max_right(int l) { return max_right(l, [](S x) { return g(x); }); } template <class G> int max_right(int l, G g) { assert(0 <= l && l <= _n); assert(g(e())); if (l == _n) return _n; l += size; for (int i = log; i >= 1; i--) push(l >> i); S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!g(op(sm, d[l]))) { while (l < size) { push(l); l = (2 * l); if (g(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template <bool (*g)(S)> int min_left(int r) { return min_left(r, [](S x) { return g(x); }); } template <class G> int min_left(int r, G g) { assert(0 <= r && r <= _n); assert(g(e())); if (r == 0) return 0; r += size; for (int i = log; i >= 1; i--) push((r - 1) >> i); S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!g(op(d[r], sm))) { while (r < size) { push(r); r = (2 * r + 1); if (g(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector<S> d; std::vector<F> lz; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } void all_apply(int k, F f) { d[k] = mapping(f, d[k]); if (k < size) lz[k] = composition(f, lz[k]); } void push(int k) { all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id(); } }; namespace internal { template <class E> struct csr { std::vector<int> start; std::vector<E> elist; csr(int n, const std::vector<std::pair<int, E>>& edges) : start(n + 1), elist(edges.size()) { for (auto e : edges) { start[e.first + 1]++; } for (int i = 1; i <= n; i++) { start[i] += start[i - 1]; } auto counter = start; for (auto e : edges) { elist[counter[e.first]++] = e.second; } } }; struct scc_graph { public: scc_graph(int n) : _n(n) {} int num_vertices() { return _n; } void add_edge(int from, int to) { edges.push_back({from, {to}}); } // @return pair of (# of scc, scc id) std::pair<int, std::vector<int>> scc_ids() { auto g = csr<edge>(_n, edges); int now_ord = 0, group_num = 0; std::vector<int> visited, low(_n), ord(_n, -1), ids(_n); visited.reserve(_n); auto dfs = [&](auto self, int v) -> void { low[v] = ord[v] = now_ord++; visited.push_back(v); for (int i = g.start[v]; i < g.start[v + 1]; i++) { auto to = g.elist[i].to; if (ord[to] == -1) { self(self, to); low[v] = std::min(low[v], low[to]); } else { low[v] = std::min(low[v], ord[to]); } } if (low[v] == ord[v]) { while (true) { int u = visited.back(); visited.pop_back(); ord[u] = _n; ids[u] = group_num; if (u == v) break; } group_num++; } }; for (int i = 0; i < _n; i++) { if (ord[i] == -1) dfs(dfs, i); } for (auto& x : ids) { x = group_num - 1 - x; } return {group_num, ids}; } std::vector<std::vector<int>> scc() { auto ids = scc_ids(); int group_num = ids.first; std::vector<int> counts(group_num); for (auto x : ids.second) counts[x]++; std::vector<std::vector<int>> groups(ids.first); for (int i = 0; i < group_num; i++) { groups[i].reserve(counts[i]); } for (int i = 0; i < _n; i++) { groups[ids.second[i]].push_back(i); } return groups; } private: int _n; struct edge { int to; }; std::vector<std::pair<int, edge>> edges; }; } struct scc_graph { public: scc_graph() : internal(0) {} scc_graph(int n) : internal(n) {} void add_edge(int from, int to) { int n = internal.num_vertices(); assert(0 <= from && from < n); assert(0 <= to && to < n); internal.add_edge(from, to); } std::vector<std::vector<int>> scc() { return internal.scc(); } private: internal::scc_graph internal; }; void conf(vs &A){ for(string i:A){ cout<<i<<' '; } cout<<endl; } void conf(vd &A){ for(double i:A){ cout<<i<<' '; } cout<<endl; } void conf(vi &A){ for(int i:A){ cout<<i<<' '; } cout<<endl; } void conf(vvvi &A,int k){ rep(0,A.size()){ jrep(0,A[i].size()){ cout<<A[i][j][k]<<' '; } cout<<endl; } } void conf(set<int> &S){ for(int i:S)cout<<i<<' '; cout<<endl; } void conf(vc &A){ for(char i:A){ cout<<i; } cout<<endl; } void conf(vb &A){ for(auto i:A){ cout<<i<<' '; } cout<<endl; } void conf(vvi &A){ rep(0,A.size()){ jrep(0,A[i].size()){ cout<<A[i][j]<<" "; } cout<<endl; } } void conf(vvd &A){ rep(0,A.size()){ jrep(0,A[i].size()){ cout<<A[i][j]<<" "; } cout<<endl; } } void conf(vvc &A){ rep(0,A.size()){ jrep(0,A[i].size()){ cout<<A[i][j]; } cout<<endl; } } void conf(vvb &A){ rep(0,A.size()){ jrep(0,A[i].size()){ cout<<(int)A[i][j]<<" "; } cout<<endl; } } void conf(vvpi &A){ rep(0,A.size()){ jrep(0,A[i].size()){ cout<<"("<<A[i][j].first<<" "<<A[i][j].second<<")"<<" "; } cout<<endl; } } void conf(vpi &A){ rep(0,A.size()){ cout <<'('<< A[i].first <<" "<<A[i].second<<')'<<" "; } cout<<endl; } int max(int a,int b){ if(a>b)return a; else return b; } int min(int a,int b){ if(a>b)return b; else return a; } int modpow(int x,int n,int mod){ int res=1; while(n>0){ int l=x%mod; if(n&1)res=(res%mod)*l%mod; x=l*l%mod; n>>=1; } return res; }//高速べき乗(modの値を返す)、計算量log(N) int ppow(int x,int n){ int res=1; while(n>0){ if(n&1)res=res*x; x=x*x; n>>=1; } return res; }//高速べき乗、計算量log(N) int modinv(int a, int m) { int b = m, u = 1, v = 0; while (b) { int t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; }//拡張EuClidの互除法、逆元を返す,a,mが互いに素ならOK、mがMOD,log(a); vi smallest_prime_factors(int n) { vi spf(n + 1); for (int i = 0; i <= n; i++) spf[i] = i; for (int i = 2; i * i <= n; i++) { if (spf[i] == i) { for (int j = i * i; j <= n; j += i) { if (spf[j] == j) { spf[j] = i; } } } } return spf; } vector<int> enumdiv(int n) { vector<int> S; for (int i = 1; 1LL*i*i <= n; i++) if (n%i == 0) { S.push_back(i); if (i*i != n) S.push_back(n / i); } sort(S.begin(), S.end()); return S; }//与えられた1つの数の約数をvectorで昇順で返す(重複なし),計算量√N vi soinsu(int N){ vi T; int n=N; int k=2; while(k*k<=n){ if(N%k==0){ N=N/k; T.push_back(k); } else{ k++; } } if(N!=1)T.push_back(N); if(T.size()==0){ T.push_back(n); } return T; }//素因数分解した結果をviで返す(sort済み),O(√N) int legendre(int N,int k){ int ans=0; int K=k; while(N>=K){ ans+=N/K; K*=k; } return ans; }//N!がkで何回割ることが出来るか vb Eratosthenes(int N){ vb IsPrime(N+1,true); IsPrime[0] = false; // 0は素数ではない IsPrime[1] = false; // 1は素数ではない for(int i=2; i*i<=N; ++i) // 0からsqrt(max)まで調べる if(IsPrime[i]) // iが素数ならば for(int j=2; i*j<=N; ++j) // (max以下の)iの倍数は IsPrime[i*j] = false; return IsPrime; }//Nまでの数が素数か素数でないかを返す、計算量nloglogn int lgcd(int A, int B){ //int a,b,C; while (A!=0 && B!=0){ if (A>B){ //a=A/B; A-=A/B*B; }else{ //b=B/A; B-=B/A*A; } //out(7) } //C=max(A,B); return max(A,B); } int lcm(int a, int b) { return a / lgcd(a, b) * b; } void YN(bool A){ if(A){ out("Yes"); }else{ out("No"); } } double max(double a,double b){ if(a>b){ return a; }else{ return b; } } double min(double a,double b){ if(a>b){ return b; }else{ return a; } } vvi mat_mul(vvi &a, vvi &b,int MOD) { vvi res(a.size(), vi(b[0].size(),0)); for (int i = 0; i < a.size(); i++) { for (int j = 0; j < b[0].size(); j++) { for (int k = 0; k < b.size(); k++) { (res[i][j] ^= a[i][k]&b[k][j]); } } } return res; } vvi mat_pow(vvi a, int n,int MOD) { int d=1; vvi res(a.size(), vi(a.size())); // 単位行列で初期化 for (int i = 0; i < a.size(); i++) res[i][i] = (d<<33)-1; // 繰り返し二乗法 while (n > 0) { if (n & 1) res = mat_mul(a, res,MOD); a = mat_mul(a, a,MOD); n >>= 1; } return res; } template <class S, S (*op)(S, S), S (*e)()> struct segtree { public: segtree() : segtree(0) {} segtree(int n) : segtree(std::vector<S>(n, e())) {} segtree(const std::vector<S>& v) : _n((v.size())) { log = ceil_pow2(_n); size = 1 << log; d = std::vector<S>(2 * size, e()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); return d[p + size]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += size; r += size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } template <bool (*f)(S)> int max_right(int l) { return max_right(l, [](S x) { return f(x); }); } template <class F> int max_right(int l, F f) { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += size; S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!f(op(sm, d[l]))) { while (l < size) { l = (2 * l); if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template <bool (*f)(S)> int min_left(int r) { return min_left(r, [](S x) { return f(x); }); } template <class F> int min_left(int r, F f) { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; r += size; S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(op(d[r], sm))) { while (r < size) { r = (2 * r + 1); if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector<S> d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } }; struct dsu { public: dsu() : _n(0) {} dsu(int n) : _n(n), parent_or_size(n, -1) {} int merge(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; return parent_or_size[a] = leader(parent_or_size[a]); } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } std::vector<std::vector<int>> groups() { std::vector<int> leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector<std::vector<int>> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }), result.end()); return result; } private: int _n; // root node: -1 * component size // otherwise: parent std::vector<int> parent_or_size; }; //NODESの大きさは((N+Q)logN) //Tはセグ木に載せる型、Fはラムダ式で演算を記述 //Nはとりあえず大きい数字を設定しておけばOK template <typename T, typename F, int NODES = 300000> struct PersistentSegmentTree { using ll = long long; struct Node { T data; Node *l, *r; Node() {} Node(const T &_data) : data(_data), l(nullptr), r(nullptr) {} }; Node *pool; int pid; ll N; const F f; const T ID; Node *nil; vector<Node *> roots; PersistentSegmentTree(const vector<T> &v, const F &f_, const T &ID_) : pid(0), f(f_), ID(ID_), nil(nullptr) { pool = new Node[NODES]; nil = my_new(ID); nil->l = nil->r = nil; roots.reserve(262144); roots.push_back(build(v)); } PersistentSegmentTree(const ll &N_, const F &f_, const T &ID_) : pid(0), N(N_), f(f_), ID(ID_), nil(nullptr) { pool = new Node[NODES]; nil = my_new(ID); nil->l = nil->r = nil; roots.reserve(262144); roots.push_back(nil); } Node *my_new(const T &data) { pool[pid].data = data; pool[pid].l = pool[pid].r = nil; return &(pool[pid++]); } Node *merge(Node *l, Node *r) { pool[pid].data = f(l->data, r->data); pool[pid].l = l; pool[pid].r = r; return &(pool[pid++]); } Node *build(const vector<T> &v) { N = (ll)v.size(); return build(0, (ll)v.size(), v); } Node *build(ll l, ll r, const vector<T> &v) { if (l + 1 == r) return my_new(v[l]); ll m = (l + r) >> 1; return merge(build(l, m, v), build(m, r, v)); } private: Node *update_(ll a, const T &x, Node *n, ll l, ll r) { if (l + 1 == r) return my_new(x); ll m = (l + r) >> 1; if (a < m) return merge(update_(a, x, n->l, l, m), n->r); return merge(n->l, update_(a, x, n->r, m, r)); } Node *add_(ll a, const T &x, Node *n, ll l, ll r) { if (l + 1 == r) return my_new(f(x, n->data)); ll m = (l + r) >> 1; if (a < m) return merge(add_(a, x, n->l, l, m), n->r); return merge(n->l, add_(a, x, n->r, m, r)); } T query_(ll a, ll b, Node *n, ll l, ll r) { if (n == nil) return ID; if (r <= a or b <= l) return ID; if (a <= l and r <= b) return n->data; ll m = (l + r) >> 1; return f(query_(a, b, n->l, l, m), query_(a, b, n->r, m, r)); } public: Node *update(Node *n, ll k, const T &x) { Node *root = update_(k, x, n, 0, N); roots.push_back(root); return root; } Node *update(int t, ll k, const T &x) { Node *root = update_(k, x, roots[t], 0, N); roots.push_back(root); return root; } Node *update(ll k, const T &x) { Node *root = update_(k, x, roots.back(), 0, N); roots.push_back(root); return root; } Node *add(Node *n, ll k, const T &x) { Node *root = add_(k, x, n, 0, N); roots.push_back(root); return root; } Node *add(int t, ll k, const T &x) { Node *root = add_(k, x, roots[t], 0, N); roots.push_back(root); return root; } Node *add(ll k, const T &x) { Node *root = add_(k, x, roots.back(), 0, N); roots.push_back(root); return root; } T query(Node *n, ll a, ll b) { return query_(a, b, n, 0, N); } T query(int t, ll a, ll b) { return query_(a, b, roots[t], 0, N); } T query(ll a, ll b) { return query_(a, b, roots.back(), 0, N); } Node *new_tree() { return nil; } }; struct UnionFind { vector<int> par, rank, siz; // 構造体の初期化 UnionFind(int n) : par(n,-1), rank(n,0), siz(n,1) { } // 根を求める int leader(int x) { if (par[x]==-1) return x; // x が根の場合は x を返す else return par[x] = leader(par[x]); // 経路圧縮 } // x と y が同じグループに属するか (= 根が一致するか) bool same(int x, int y) { return leader(x)==leader(y); } // x を含むグループと y を含むグループを併合する bool merge(int x, int y) { int rx = leader(x), ry = leader(y); // x 側と y 側の根を取得する if (rx==ry) return false; // すでに同じグループのときは何もしない // union by rank par[ry] = rx; // ry を rx の子とする siz[rx] += siz[ry]; // rx 側の siz を調整する return true; } // x を含む根付き木のサイズを求める int size(int x) { return siz[leader(x)]; } }; vi dikstra(int s,int V,vvpi &G){ vi d(V,BIG); priority_queue<Pi,vector<Pi>,greater<Pi>> que; d[s]=0; que.push(Pi(0,s));//Pi(距離、向かう頂点) while(!que.empty()){ Pi p=que.top();que.pop(); int v=p.second; if(d[v]<p.first)continue; rep(0,G[v].size()){ int a=G[v][i].second; int b=G[v][i].first; if(d[a]>d[v]+b){ d[a]=d[v]+b; que.push(Pi(d[a],a)); } } } return d; }//始点は0start int op(int a, int b) { return max(a,b); } int e() { return 0; } //int target; //bool f(int v) { return v >= target; } struct loopdfs{ public: int flgggg; bool gg; bool x; int start; loopdfs(int n){ flgggg=-1; gg=false; x=false; start=n;//0-indexed }; void loops(int a,vvi &G,vb &seen,vi &loop,vi &prev){ seen[a]=true; for (auto nv : G[a]) { if(gg)continue; if (seen[nv]){ flgggg=nv; gg=true; x=true; break; } loops(nv,G,seen,loop,prev); } if(!gg&&x){ prev.push_back(a); } if(gg){ loop.push_back(a); } if(flgggg==a)gg=false; if(a==start){ reverse(loop.begin(),loop.end()); reverse(prev.begin(),prev.end()); } }//有向なfunctional graphのみ動作確認、 }; vvi calcNext(const string &S) { int n = (int)S.size(); vector<vector<int> > res(n+1, vector<int>(26, n)); for (int i = n-1; i >= 0; --i) { for (int j = 0; j < 26; ++j) res[i][j] = res[i+1][j]; res[i][S[i]-'a'] = i; } return res; } struct S{ int v; //int size; };/* S op(S a,S b){ return {min(a.v,b.v)}; } S e(){ return {BIG}; } S mapping(int a, S b){ return {a+b.v}; } int composition(int a,int b){ return a+b; } int id(){return 0;}*/ vi compress(vi &A){ vi vals=A; sot(vals); vals.erase(unique(vals.begin(), vals.end()), vals.end()); vi X(A.size()); rep(0,A.size()){ X[i]=lower_bound(vals.begin(),vals.end(),A[i])-vals.begin(); } return X; }//0-indexed template <typename T> vector<T> compress(vector<T> &C1, vector<T> &C2,int w) { vector<T> vals; int N = (int)C1.size(); for (int i = 0; i < N; i++) { for (int d = 0; d <= 0; d++) { // for (T d = 0; d <= 0; d++) でも良い T tc1 = C1[i] - d; if(tc1>=0){ vals.push_back(tc1); } T tc2 = C2[i] + d; if(tc2<=w){ vals.push_back(tc2); } } } sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); for (int i = 0; i < N; i++) { C1[i] = lower_bound(vals.begin(), vals.end(), C1[i]) - vals.begin(); C2[i] = lower_bound(vals.begin(), vals.end(), C2[i]) - vals.begin(); } return vals; }//2次元座標圧縮 int kruskal(vector<TPi> &A,int V){ rsot(A); int M=A.size(); dsu uf(V); int res=0; rep(0,M){ int a=get<1>(A[i]);int b=get<2>(A[i]); int c=get<0>(A[i]); if(!uf.same(a,b)){ uf.merge(a,b); res+=c; } } bool flag=false; rep(0,V){ if(!uf.same(i,0))flag=true; } if(flag){ res=-1; } return res; } string encode(string& str) { string ret = ""; // 答えを格納 int n=(int)(str.size()); for (int l = 0; l < n;) { int r = l + 1; while(r < n && str[l] == str[r]){ r++; } ret.push_back(str[l]); char num_str = (char)((r - l)+'0'); // 出現回数 ret += num_str; l = r; } return ret; } bool revsort(const Pi &a,const Pi &b){ if(a.first>b.first){ return true; }else{ if(a.first==b.first){ if(a.second<b.second){ return true; }else{ return false; } }else{ return false; } } }//Piでfirst降順、second昇順 bool anglesortbool(const Pi &a,const Pi &b){ int x=a.first*b.second-a.second*b.first; if(x>0){ return true; }else{ return false; } } vpi anglesort(vpi &A){ vvpi qua(4); rep(0,A.size()){ int x=A[i].first;int y=A[i].second; if(x>0&&y>=0){ qua[0].push_back(Pi(x,y)); } if(x<=0&&y>0){ qua[1].push_back(Pi(x,y)); } if(x<0&&y<=0){ qua[2].push_back(Pi(x,y)); } if(x>=0&&y<0){ qua[3].push_back(Pi(x,y)); } } rep(0,4){ sort(qua[i].begin(),qua[i].end(),anglesortbool); } vpi B; rep(0,4){ jrep(0,qua[i].size()){ B.pb(qua[i][j]); } } return B; }//偏角ソート、pairの値は10^9まで、0から2Πを昇順にソート void predfs1(vvb &G,int h,int w,int H,int W){ if(G[h][w])return; G[h][w]=true; vi dh={1,0,-1,0}; vi dw={0,1,0,-1}; rep(0,4){ int x=h+dh[i];int y=w+dw[i]; if(x>=0&&x<=H-1&&y>=0&&y<=W-1&&(!G[x][y])){ predfs1(G,x,y,H,W); // 再帰的に探索 } } } void predfs(vb &seen,int a,vvi &G){ if(seen[a])return; seen[a]=true; for(int i:G[a]){ if(seen[i])continue; predfs(seen,i,G); // 再帰的に探索 } } int bdp2(int N,int bit,vi &dp,vb &seen){ if(seen[bit]){ //out(7) return dp[bit]; } //out(7) int res = dp[bit]; brep((1<<N),0){ i&=bit; int pbit=bit&(~i); if(i==0||pbit==0)continue; //dout(bit,pbit) res=min(bdp2(N,i,dp,seen)+bdp2(N,pbit,dp,seen),res); } seen[bit]=true; return dp[bit]=res; // メモしながらリターン } vvi prebfs1(vvc &G,vvi &A,int h,int w,int H,int W){ vi dh={1,0,-1,0}; vi dw={0,1,0,-1}; A[h][w]=0; queue<Pi> que; que.push(Pi(h,w)); while(!que.empty()){ Pi v=que.front();que.pop(); rep(0,4){ int x=v.first+dh[i];int y=v.second+dw[i]; if(x>=0&&x<=H-1&&y>=0&&y<=W-1&&(A[x][y]==-1)&&G[x][y]!='#'){ que.push(Pi(x,y)); A[x][y]=A[v.first][v.second]+1; } } } return A; } vi prebfs(vvi &G,int a,int N){ vi dist(N, -1); // 全頂点を「未訪問」に初期化 queue<int> que; dist[a] = 0; que.push(a); // 0 を橙色頂点にする while (!que.empty()) { int v = que.front(); // キューから先頭頂点を取り出す que.pop(); for (int nv : G[v]) { if (dist[nv] != -1) continue; dist[nv] = dist[v] + 1; que.push(nv); } } return dist; } signed main(){ int N,M;cin>>N>>M; dsu uf(N); vi inv(N,0); vi siz(N,0); rep(0,M){ int a,b;cin>>a>>b;a--;b--; uf.merge(a,b); siz[a]++; inv[b]++; //G[b].pb(a); } int h=0; int g=0; int cnt=0; bool gy=true; int el=0; int gk=0; vvi X=uf.groups(); //conf(X); int ans=0; rep(0,X.size()){ int hh=0; int gg=0; if(X[i].size()==1){ if(siz[X[i][0]]==0&&inv[X[i][0]]==0)continue; } bool r=true; //if(X[i].size()==1)dout(siz[X[i][0]],inv[X[i][0]]) for(int v:X[i]){ if(siz[v]!=inv[v])r=false; if(siz[v]>inv[v])hh+=siz[v]-inv[v]; else gg+=inv[v]-siz[v]; } h+=hh; g+=gg; ans+=max(hh-1,0); cnt++; } //dout(ans,cnt) if(cnt!=1)out(ans+cnt) else out(cnt-1+ans) }