結果
問題 | No.2160 みたりのDominator |
ユーザー | 👑 Nachia |
提出日時 | 2022-12-11 15:05:03 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 14,407 bytes |
コンパイル時間 | 1,686 ms |
コンパイル使用メモリ | 104,604 KB |
実行使用メモリ | 36,816 KB |
最終ジャッジ日時 | 2024-10-15 12:11:38 |
合計ジャッジ時間 | 9,736 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 41 ms
19,640 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | AC | 2 ms
5,248 KB |
testcase_15 | AC | 2 ms
5,248 KB |
testcase_16 | AC | 2 ms
5,248 KB |
testcase_17 | AC | 2 ms
5,248 KB |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | AC | 2 ms
5,248 KB |
testcase_20 | AC | 2 ms
5,248 KB |
testcase_21 | AC | 2 ms
5,248 KB |
testcase_22 | AC | 2 ms
5,248 KB |
testcase_23 | AC | 2 ms
5,248 KB |
testcase_24 | AC | 2 ms
5,248 KB |
testcase_25 | AC | 2 ms
5,248 KB |
testcase_26 | AC | 2 ms
5,248 KB |
testcase_27 | AC | 2 ms
5,248 KB |
testcase_28 | AC | 2 ms
5,248 KB |
testcase_29 | AC | 2 ms
5,248 KB |
testcase_30 | AC | 2 ms
5,248 KB |
testcase_31 | AC | 2 ms
5,248 KB |
testcase_32 | AC | 2 ms
5,248 KB |
testcase_33 | AC | 2 ms
5,248 KB |
testcase_34 | AC | 43 ms
19,644 KB |
testcase_35 | AC | 2 ms
5,248 KB |
testcase_36 | AC | 2 ms
5,248 KB |
testcase_37 | AC | 2 ms
5,248 KB |
testcase_38 | AC | 2 ms
5,248 KB |
testcase_39 | AC | 2 ms
5,248 KB |
testcase_40 | AC | 50 ms
18,728 KB |
testcase_41 | AC | 47 ms
18,692 KB |
testcase_42 | AC | 29 ms
12,512 KB |
testcase_43 | AC | 39 ms
15,756 KB |
testcase_44 | AC | 49 ms
18,412 KB |
testcase_45 | AC | 47 ms
18,256 KB |
testcase_46 | AC | 42 ms
17,372 KB |
testcase_47 | AC | 24 ms
11,984 KB |
testcase_48 | AC | 32 ms
14,764 KB |
testcase_49 | AC | 37 ms
17,872 KB |
testcase_50 | AC | 36 ms
17,912 KB |
testcase_51 | AC | 31 ms
13,580 KB |
testcase_52 | AC | 43 ms
17,712 KB |
testcase_53 | AC | 48 ms
18,096 KB |
testcase_54 | AC | 28 ms
12,080 KB |
testcase_55 | AC | 91 ms
33,068 KB |
testcase_56 | AC | 81 ms
31,480 KB |
testcase_57 | AC | 83 ms
31,888 KB |
testcase_58 | AC | 94 ms
35,792 KB |
testcase_59 | AC | 89 ms
33,004 KB |
testcase_60 | AC | 88 ms
36,452 KB |
testcase_61 | AC | 89 ms
32,588 KB |
testcase_62 | AC | 103 ms
36,816 KB |
testcase_63 | AC | 92 ms
33,632 KB |
testcase_64 | AC | 76 ms
32,972 KB |
testcase_65 | AC | 46 ms
19,280 KB |
testcase_66 | AC | 48 ms
20,176 KB |
testcase_67 | AC | 49 ms
20,684 KB |
testcase_68 | AC | 92 ms
33,744 KB |
testcase_69 | AC | 69 ms
25,812 KB |
testcase_70 | AC | 92 ms
33,748 KB |
testcase_71 | AC | 39 ms
16,380 KB |
testcase_72 | AC | 72 ms
26,604 KB |
testcase_73 | AC | 92 ms
33,316 KB |
testcase_74 | AC | 88 ms
31,956 KB |
testcase_75 | AC | 20 ms
11,988 KB |
testcase_76 | AC | 17 ms
10,196 KB |
testcase_77 | AC | 58 ms
23,292 KB |
testcase_78 | AC | 70 ms
25,932 KB |
testcase_79 | AC | 12 ms
7,960 KB |
testcase_80 | AC | 14 ms
9,108 KB |
testcase_81 | AC | 25 ms
13,724 KB |
testcase_82 | AC | 28 ms
15,440 KB |
testcase_83 | AC | 31 ms
15,704 KB |
61_evil_bias_nocross_01.txt | AC | 49 ms
18,856 KB |
61_evil_bias_nocross_02.txt | AC | 48 ms
18,688 KB |
61_evil_bias_nocross_03.txt | AC | 27 ms
12,468 KB |
61_evil_bias_nocross_04.txt | AC | 38 ms
15,752 KB |
61_evil_bias_nocross_05.txt | AC | 47 ms
18,284 KB |
61_evil_bias_nocross_06.txt | AC | 49 ms
18,804 KB |
61_evil_bias_nocross_07.txt | AC | 31 ms
13,576 KB |
61_evil_bias_nocross_08.txt | AC | 44 ms
17,712 KB |
61_evil_bias_nocross_09.txt | AC | 46 ms
18,224 KB |
61_evil_bias_nocross_10.txt | AC | 27 ms
12,208 KB |
61_evil_bias_nocross_11.txt | AC | 36 ms
15,328 KB |
61_evil_bias_nocross_12.txt | AC | 43 ms
17,124 KB |
ソースコード
#line 1 "Main.cpp" #include <iostream> #include <string> #include <vector> #include <algorithm> #include <utility> #line 4 "nachia\\graph\\graph.hpp" #include <cassert> #line 5 "nachia\\array\\csr-array.hpp" namespace nachia{ template<class Elem> class CsrArray{ public: struct ListRange{ using iterator = typename std::vector<Elem>::iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } Elem& operator[](int i) const { return begi[i]; } }; struct ConstListRange{ using iterator = typename std::vector<Elem>::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const Elem& operator[](int i) const { return begi[i]; } }; private: int m_n; std::vector<Elem> m_list; std::vector<int> m_pos; public: CsrArray() : m_n(0), m_list(), m_pos() {} static CsrArray Construct(int n, std::vector<std::pair<int, Elem>> items){ CsrArray res; res.m_n = n; std::vector<int> buf(n+1, 0); for(auto& [u,v] : items){ ++buf[u]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.m_list.resize(buf[n]); for(int i=(int)items.size()-1; i>=0; i--){ res.m_list[--buf[items[i].first]] = std::move(items[i].second); } res.m_pos = std::move(buf); return res; } static CsrArray FromRaw(std::vector<Elem> list, std::vector<int> pos){ CsrArray res; res.m_n = pos.size() - 1; res.m_list = std::move(list); res.m_pos = std::move(pos); return res; } ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } int size() const { return m_n; } int fullSize() const { return (int)m_list.size(); } }; } // namespace nachia #line 6 "nachia\\graph\\graph.hpp" namespace nachia{ struct Graph { public: struct Edge{ int from, to; void reverse(){ std::swap(from, to); } }; using Base = std::vector<std::pair<int, int>>; Graph(int n = 0, bool undirected = false) : m_n(n), m_e(), m_isUndir(undirected) {} Graph(int n, const std::vector<std::pair<int, int>>& edges, bool undirected = false) : m_n(n), m_isUndir(undirected){ m_e.resize(edges.size()); for(std::size_t i=0; i<edges.size(); i++) m_e[i] = { edges[i].first, edges[i].second }; } Graph(int n, const std::vector<Edge>& edges, bool undirected = false) : m_n(n), m_e(edges), m_isUndir(undirected) {} Graph(int n, std::vector<Edge>&& edges, bool undirected = false) : m_n(n), m_e(edges), m_isUndir(undirected) {} int numVertices() const noexcept { return m_n; } int numEdges() const noexcept { return int(m_e.size()); } int addNode() noexcept { return m_n++; } int addEdge(int from, int to){ m_e.push_back({ from, to }); return numEdges() - 1; } Edge& operator[](int ei) noexcept { return m_e[ei]; } const Edge& operator[](int ei) const noexcept { return m_e[ei]; } Edge& at(int ei) { return m_e.at(ei); } const Edge& at(int ei) const { return m_e.at(ei); } auto begin(){ return m_e.begin(); } auto end(){ return m_e.end(); } auto begin() const { return m_e.begin(); } auto end() const { return m_e.end(); } bool isUndirected() const noexcept { return m_isUndir; } void reverseEdges() noexcept { for(auto& e : m_e) e.reverse(); } void contract(int newV, const std::vector<int>& mapping){ assert(numVertices() == int(mapping.size())); for(int i=0; i<numVertices(); i++) assert(0 <= mapping[i] && mapping[i] < newV); for(auto& e : m_e){ e.from = mapping[e.from]; e.to = mapping[e.to]; } } std::vector<Graph> induce(int num, const std::vector<int>& mapping) const { int n = numVertices(); assert(n == int(mapping.size())); for(int i=0; i<n; i++) assert(-1 <= mapping[i] && mapping[i] < num); std::vector<int> indexV(n), newV(num); for(int i=0; i<n; i++) if(mapping[i] >= 0) indexV[i] = newV[mapping[i]]++; std::vector<Graph> res; res.reserve(num); for(int i=0; i<num; i++) res.emplace_back(newV[i], isUndirected()); for(auto e : m_e) if(mapping[e.from] == mapping[e.to] && mapping[e.to] >= 0) res[mapping[e.to]].addEdge(indexV[e.from], indexV[e.to]); return res; } CsrArray<int> getEdgeIndexArray(bool undirected) const { std::vector<std::pair<int, int>> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(int i=0; i<numEdges(); i++){ auto e = operator[](i); src.emplace_back(e.from, i); if(undirected) src.emplace_back(e.to, i); } return CsrArray<int>::Construct(numVertices(), src); } CsrArray<int> getEdgeIndexArray() const { return getEdgeIndexArray(isUndirected()); } CsrArray<int> getAdjacencyArray(bool undirected) const { std::vector<std::pair<int, int>> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(auto e : m_e){ src.emplace_back(e.from, e.to); if(undirected) src.emplace_back(e.to, e.from); } return CsrArray<int>::Construct(numVertices(), src); } CsrArray<int> getAdjacencyArray() const { return getAdjacencyArray(isUndirected()); } private: int m_n; std::vector<Edge> m_e; bool m_isUndir; }; } // namespace nachia #line 4 "nachia\\graph\\strongly-connected-components.hpp" namespace nachia{ struct StronglyConnectedComponents{ int m_n; CsrArray<int> induce; int componentNum; StronglyConnectedComponents() : m_n(0), induce(), componentNum(0) {} StronglyConnectedComponents(Graph E) { int n = E.numVertices(); m_n = n; std::vector<int> O(n); { auto adj = E.getAdjacencyArray(); int Oi = n; std::vector<int> P(n, -1), EI(n, 0); for(int s=0; s<n; s++) if(P[s] == -1){ P[s] = -2; int p = s; while(p >= 0){ if(EI[p] == adj[p].size()){ O[--Oi] = p; p = P[p]; continue; } int q = adj[p][EI[p]++]; if(P[q] == -1){ P[q] = p; p = q; } } } } E.reverseEdges(); auto adj = E.getAdjacencyArray(); std::vector<int> sep = {0}, csr(n), vis(n,0); int p1 = 0, p2 = 0; for(int s : O) if(!vis[s]){ csr[p2++] = s; vis[s] = 1; for(; p1<p2; p1++){ int v = csr[p1]; for(auto e : adj[v]) if(!vis[e]){ vis[e] = 1; csr[p2++] = e; } } sep.push_back(p2); } induce = CsrArray<int>::FromRaw(std::move(csr), std::move(sep)); componentNum = induce.size(); } int numComponent() const { return componentNum; } const CsrArray<int>& getCsr() const { return induce; } }; } // namespace nachia #line 2 "nachia\\misc\\fastio.hpp" #include <cstdio> #include <cctype> #include <cstdint> #line 6 "nachia\\misc\\fastio.hpp" namespace nachia{ struct CInStream{ private: static const unsigned int INPUT_BUF_SIZE = 1 << 17; unsigned int p = INPUT_BUF_SIZE; static char Q[INPUT_BUF_SIZE]; public: using MyType = CInStream; char seekChar(){ if(p == INPUT_BUF_SIZE){ size_t len = fread(Q, 1, INPUT_BUF_SIZE, stdin); if(len != INPUT_BUF_SIZE) Q[len] = '\0'; p = 0; } return Q[p]; } void skipSpace(){ while(isspace(seekChar())) p++; } uint32_t nextU32(){ skipSpace(); uint32_t buf = 0; while(true){ char tmp = seekChar(); if('9' < tmp || tmp < '0') break; buf = buf * 10 + (tmp - '0'); p++; } return buf; } int32_t nextI32(){ skipSpace(); if(seekChar() == '-'){ p++; return (int32_t)(-nextU32()); } return (int32_t)nextU32(); } uint64_t nextU64(){ skipSpace(); uint64_t buf = 0; while(true){ char tmp = seekChar(); if('9' < tmp || tmp < '0') break; buf = buf * 10 + (tmp - '0'); p++; } return buf; } int64_t nextI64(){ skipSpace(); if(seekChar() == '-'){ p++; return (int64_t)(-nextU64()); } return (int64_t)nextU64(); } char nextChar(){ skipSpace(); char buf = seekChar(); p++; return buf; } std::string nextToken(){ skipSpace(); std::string buf; while(true){ char ch = seekChar(); if(isspace(ch) || ch == '\0') break; buf.push_back(ch); p++; } return buf; } MyType& operator>>(unsigned int& dest){ dest = nextU32(); return *this; } MyType& operator>>(int& dest){ dest = nextI32(); return *this; } MyType& operator>>(unsigned long& dest){ dest = nextU64(); return *this; } MyType& operator>>(long& dest){ dest = nextI64(); return *this; } MyType& operator>>(unsigned long long& dest){ dest = nextU64(); return *this; } MyType& operator>>(long long& dest){ dest = nextI64(); return *this; } MyType& operator>>(std::string& dest){ dest = nextToken(); return *this; } MyType& operator>>(char& dest){ dest = nextChar(); return *this; } } cin; struct FastOutputTable{ char LZ[1000][4] = {}; char NLZ[1000][4] = {}; constexpr FastOutputTable(){ using u32 = uint_fast32_t; for(u32 d=0; d<1000; d++){ LZ[d][0] = ('0' + d / 100 % 10); LZ[d][1] = ('0' + d / 10 % 10); LZ[d][2] = ('0' + d / 1 % 10); LZ[d][3] = '\0'; } for(u32 d=0; d<1000; d++){ u32 i = 0; if(d >= 100) NLZ[d][i++] = ('0' + d / 100 % 10); if(d >= 10) NLZ[d][i++] = ('0' + d / 10 % 10); if(d >= 1) NLZ[d][i++] = ('0' + d / 1 % 10); NLZ[d][i++] = '\0'; } } }; struct COutStream{ private: using u32 = uint32_t; using u64 = uint64_t; using MyType = COutStream; static const u32 OUTPUT_BUF_SIZE = 1 << 17; static char Q[OUTPUT_BUF_SIZE]; static constexpr FastOutputTable TB = FastOutputTable(); u32 p = 0; static constexpr u32 P10(u32 d){ return d ? P10(d-1)*10 : 1; } static constexpr u64 P10L(u32 d){ return d ? P10L(d-1)*10 : 1; } template<class T, class U> static void Fil(T& m, U& l, U x) noexcept { m = l/x; l -= m*x; } void next_dig9(u32 x){ u32 y; Fil(y, x, P10(6)); nextCstr(TB.LZ[y]); Fil(y, x, P10(3)); nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]); } public: void nextChar(char c){ Q[p++] = c; if(p == OUTPUT_BUF_SIZE){ fwrite(Q, p, 1, stdout); p = 0; } } void nextEoln(){ nextChar('\n'); } void nextCstr(const char* s){ while(*s) nextChar(*(s++)); } void nextU32(uint32_t x){ u32 y = 0; if(x >= P10(9)){ Fil(y, x, P10(9)); nextCstr(TB.NLZ[y]); next_dig9(x); } else if(x >= P10(6)){ Fil(y, x, P10(6)); nextCstr(TB.NLZ[y]); Fil(y, x, P10(3)); nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]); } else if(x >= P10(3)){ Fil(y, x, P10(3)); nextCstr(TB.NLZ[y]); nextCstr(TB.LZ[x]); } else if(x >= 1) nextCstr(TB.NLZ[x]); else nextChar('0'); } void nextI32(int32_t x){ if(x >= 0) nextU32(x); else{ nextChar('-'); nextU32((u32)-x); } } void nextU64(uint64_t x){ u32 y = 0; if(x >= P10L(18)){ Fil(y, x, P10L(18)); nextU32(y); Fil(y, x, P10L(9)); next_dig9(y); next_dig9(x); } else if(x >= P10L(9)){ Fil(y, x, P10L(9)); nextU32(y); next_dig9(x); } else nextU32(x); } void nextI64(int64_t x){ if(x >= 0) nextU64(x); else{ nextChar('-'); nextU64((u64)-x); } } void writeToFile(bool flush = false){ fwrite(Q, p, 1, stdout); if(flush) fflush(stdout); p = 0; } COutStream(){ Q[0] = 0; } ~COutStream(){ writeToFile(); } MyType& operator<<(unsigned int tg){ nextU32(tg); return *this; } MyType& operator<<(unsigned long tg){ nextU64(tg); return *this; } MyType& operator<<(unsigned long long tg){ nextU64(tg); return *this; } MyType& operator<<(int tg){ nextI32(tg); return *this; } MyType& operator<<(long tg){ nextI64(tg); return *this; } MyType& operator<<(long long tg){ nextI64(tg); return *this; } MyType& operator<<(const std::string& tg){ nextCstr(tg.c_str()); return *this; } MyType& operator<<(const char* tg){ nextCstr(tg); return *this; } MyType& operator<<(char tg){ nextChar(tg); return *this; } } cout; char CInStream::Q[INPUT_BUF_SIZE]; char COutStream::Q[OUTPUT_BUF_SIZE]; } // namespace nachia #line 9 "Main.cpp" int main(){ using nachia::cin; using nachia::cout; int N1, N2, N3, M; cin >> N1 >> N2 >> N3 >> M; int s = N1+N2+N3, t = N1+N2+N3+1, N = N1+N2+N3+2; nachia::Graph graph(N, false); if(N1 != 0){ graph.addEdge(s, 0); for(int i=0; i<N1-1; i++) graph.addEdge(i,i+1); graph.addEdge(N1-1, t); } else { graph.addEdge(s, t); } if(N2 != 0){ graph.addEdge(s, N1); for(int i=N1; i<N1+N2-1; i++) graph.addEdge(i,i+1); graph.addEdge(N1+N2-1, t); } else { graph.addEdge(s, t); } if(N3 != 0){ graph.addEdge(s, N1+N2); for(int i=N1+N2; i<N1+N2+N3-1; i++) graph.addEdge(i,i+1); graph.addEdge(N1+N2+N3-1, t); } else { graph.addEdge(s, t); } for(int i=0; i<M; i++){ int u, v; cin >> u >> v; u--; v--; graph.addEdge(u, v); graph.addEdge(v, u); } auto scc = nachia::StronglyConnectedComponents(graph).getCsr(); std::vector<int> sccid(N); for(int i=0; i<scc.size(); i++) for(int j : scc[i]) sccid[j] = i; N = scc.size(); s = sccid[s]; t = sccid[t]; if(s == t){ cout << "0\n"; return 0; } nachia::Graph graph2(N, false); for(auto e : graph) if(sccid[e.from] != sccid[e.to]) graph2.addEdge(sccid[e.from], sccid[e.to]); std::vector<int> SkipV(N, -1); auto adj_graph2d = graph2.getAdjacencyArray(false); int N4 = 0; for(int i=0; i<N; i++) if(adj_graph2d[i].size() != 1) SkipV[i] = N4++; std::vector<long long> partAns(N4-1, 1); for(int v=0; v<N; v++) if(SkipV[v] != -1) for(int w : adj_graph2d[v]){ int weight = 1; while(SkipV[w] == -1){ w = adj_graph2d[w][0]; weight++; } int vp = SkipV[v], wp = SkipV[w]; for(int i=vp; i<wp; i++) partAns[i] *= weight; } long long ans = 0; for(auto w : partAns) ans += w; cout << ans << '\n'; return 0; }