Guest User

Untitled

a guest
Mar 1st, 2020
38
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //#define ONLINE_JUDGE
  2.  
  3. #if defined(ONLINE_JUDGE)
  4. #define _SECURE_SCL 0
  5. #endif
  6.  
  7. #include <iostream>
  8. #include <iomanip>
  9. #include <string>
  10. #include <sstream>
  11. #include <fstream>
  12. #include <algorithm>
  13. #include <vector>
  14. #include <deque>
  15. #include <set>
  16. #include <map>
  17. #include <functional>
  18. #include <memory>
  19. #include <cmath>
  20. #include <climits>
  21. #include <numeric>
  22. #include <tuple>
  23. #include <random>
  24. #include <memory.h>
  25. #include <stdint.h>
  26.  
  27. #if !defined(__GNUC__)
  28. #else // !defined(__GNUC__)
  29. #define _CrtDbgBreak() __builtin_trap()
  30. #endif // !defined(__GNUC__)
  31.  
  32. #if defined(ONLINE_JUDGE)
  33. #define LOCAL_TEST 0
  34. #else
  35. #define LOCAL_TEST 1
  36. #endif
  37.  
  38. template<typename T1, typename T2> auto Endl(std::basic_ostream<T1, T2>& ostr) -> decltype(std::endl<T1, T2>(ostr)) {
  39.     return std::endl<T1, T2>(ostr);
  40. }
  41.  
  42. #if LOCAL_TEST
  43. struct AssertsCounter
  44. {
  45.     AssertsCounter(): counter(0) {}
  46.     ~AssertsCounter() { std::cerr << Endl << "DIAG: " << (counter == 0 ? "OK" : "FAIL!!!") << " Asserts count: " << counter << Endl; }
  47.     void Increment() { counter++; }
  48.     uint32_t counter;
  49. };
  50. AssertsCounter g_assertsCounter;
  51. #define LOCAL_ASSERT(expr) { if (!(expr)) {std::cerr << "ASSERT FAILED (" << __LINE__ << "): '" << #expr << "'" << Endl; g_assertsCounter.Increment(); _CrtDbgBreak(); } }
  52. #define LOCAL_ASSERT_EQ(expr1, expr2) { if ((expr1) != (expr2)) {std::cerr << "ASSERT FAILED (" << __LINE__ << "): '" << #expr1 << "' == '" << #expr2 << "' (" << (expr1) << " vs " << (expr2) << "')" << Endl; g_assertsCounter.Increment(); _CrtDbgBreak(); } }
  53. #else
  54. volatile bool isLocalTestEnabled = 0;
  55. #define LOCAL_ASSERT(expr)
  56. #define LOCAL_ASSERT_EQ(expr1, expr2)
  57. #endif
  58.  
  59. bool g_isLocalPrintEnabled = (bool)(LOCAL_TEST);
  60. #define LOCAL_PRINT() if (!g_isLocalPrintEnabled) { } else std::cerr // << .. << ..
  61.  
  62. typedef std::string string8_t;
  63. typedef long double ld_t;
  64.  
  65. typedef std::vector<size_t> vector_size_t;
  66. typedef std::vector<uint8_t> vector_uint8_t;
  67. typedef std::vector<int32_t> vector_int32_t;
  68. typedef std::vector<uint32_t> vector_uint32_t;
  69. typedef std::vector<int64_t> vector_int64_t;
  70. typedef std::vector<uint64_t> vector_uint64_t;
  71. typedef std::vector<string8_t> vector_string8_t;
  72.  
  73. typedef std::vector<vector_size_t> vector_2d_size_t;
  74. typedef std::vector<vector_int32_t> vector_2d_int32_t;
  75. typedef std::vector<vector_uint32_t> vector_2d_uint32_t;
  76. typedef std::vector<vector_int64_t> vector_2d_int64_t;
  77. typedef std::vector<vector_uint64_t> vector_2d_uint64_t;
  78.  
  79. typedef std::set<size_t> set_size_t;
  80. typedef std::set<int32_t> set_int32_t;
  81. typedef std::set<uint32_t> set_uint32_t;
  82. typedef std::set<int64_t> set_int64_t;
  83. typedef std::set<uint64_t> set_uint64_t;
  84. typedef std::set<string8_t> set_string8_t;
  85.  
  86. typedef std::multiset<size_t> multiset_size_t;
  87. typedef std::multiset<string8_t> multiset_string8_t;
  88.  
  89. // Auxiliary functions definition
  90. //
  91. template<typename T> void UpdateMin(T& a, const T b) {a = std::min(a, b);}
  92. template<typename T> void UpdateMax(T& a, const T b) {a = std::max(a, b);}
  93.  
  94. const ld_t Pi = std::atan(1.0L) * 4.0L;
  95. static const ld_t Eps = 1.0e-09;
  96. template<typename T> bool IsEqual(const T a, const T b) { return std::abs(a - b) < Eps; }
  97. template<typename T> bool IsGreater(const T a, const T b) { return a > b + Eps; }
  98. template<typename T> bool IsLess(const T a, const T b) { return a + Eps < b; }
  99. template<typename T> bool IsGreaterEqual(const T a, const T b) { return !IsLess(a, b); }
  100. template<typename T> bool IsLessEqual(const T a, const T b) { return !IsGreater(a, b); }
  101.  
  102. template<typename T> string8_t ToStr(const T& val) { std::ostringstream ostr; ostr << val; return ostr.str(); }
  103. template<typename T> bool FromStr(const string8_t& str, T& val) {std::istringstream istr(str); istr >> val; return !!istr; }
  104. template<typename T> T FromStr(const string8_t& str) {T val = {}; std::istringstream istr(str); istr >> val; return val; }
  105.  
  106. template<typename ContainerType, typename ValueType> bool Contains(const ContainerType& c, const ValueType& v) { return c.find(v) != c.end(); }
  107.  
  108. uint64_t SafeAdd(uint64_t a, uint64_t b) { uint64_t M = std::numeric_limits<uint64_t>::max(); return a <= M - b ? a + b : M; }
  109. uint64_t SafeMul(uint64_t a, uint64_t b) { uint64_t M = std::numeric_limits<uint64_t>::max(); return a <= M / b ? a * b : M; }
  110.  
  111. template<typename T> std::istream& operator>>(std::istream& ist, std::vector<T>& data)
  112. {
  113.     LOCAL_ASSERT(!!ist);
  114.     for (size_t i = 0; i < data.size(); i++) { ist >> data[i]; }
  115.     return ist;
  116. }
  117.  
  118. template<typename T> T Read(std::istream& ist)
  119. {
  120.     LOCAL_ASSERT(!!ist);
  121.     T val; ist >> val; return val;
  122. }
  123.  
  124. template<typename T> std::ostream& operator<<(std::ostream& ost, const std::vector<T>& data)
  125. {
  126.     for (size_t i = 0; i < data.size(); i++) { if (i != 0) { ost << ' '; } ost << data[i]; }
  127.     return ost;
  128. }
  129.  
  130. #if defined(ONLINE_JUDGE)
  131. template<size_t id> class StopWatch { };
  132. #else
  133. #include <library/lib_stopwatch.h>
  134. #include <library/lib_random.h>
  135. library::random::Rand g_rnd;
  136. #endif
  137.  
  138. void Wave(const vector_2d_size_t& links, const size_t start, vector_size_t& distances) {
  139.     vector_size_t isVisited(links.size());
  140.  
  141.     size_t currentDistance = 0;
  142.     isVisited[start] = 1;
  143.     distances[start] = 0;
  144.     std::deque<size_t> q;
  145.     q.emplace_back(start);
  146.  
  147.     while (!q.empty()) {
  148.         currentDistance += 1;
  149.         std::deque<size_t> nq;
  150.         for (const auto qi : q) {
  151.             for (const auto v : links[qi]) {
  152.                 if (!isVisited[v]) {
  153.                     nq.emplace_back(v);
  154.                     isVisited[v] = 1;
  155.                     distances[v] = currentDistance;
  156.                 }
  157.             }
  158.         }
  159.         q.swap(nq);
  160.     }
  161. }
  162.  
  163. bool IsAmbigous(const vector_2d_size_t& links, const size_t v, const vector_size_t& distances) {
  164.     size_t minDistance = std::numeric_limits<size_t>::max();
  165.     size_t minCount = 0;
  166.     for (size_t vi : links[v]) {
  167.         if (distances[vi] < minDistance) {
  168.             minDistance = distances[vi];
  169.             minCount = 1;
  170.         } else if (distances[vi] == minDistance) {
  171.             minCount += 1;
  172.         }
  173.     }
  174.     if (minCount == 0) {
  175.         return false;
  176.     }
  177.     return minCount != 1;
  178. }
  179.  
  180. bool Solve(std::istream& ist, std::ostream& ost, const bool multipleTestMode)
  181. {
  182.     StopWatch<1> sw; (void)sw;
  183.  
  184.     //
  185.     size_t n, m;
  186.     ist >> n >> m;
  187.  
  188.     if (multipleTestMode && !ist)
  189.         return false;
  190.  
  191.     //
  192.     LOCAL_PRINT() << Endl << "Next test" << Endl;
  193.     vector_2d_size_t flinks(n);
  194.     vector_2d_size_t rlinks(n);
  195.     for (size_t i = 0; i < m; i++) {
  196.         size_t u, v;
  197.         ist >> u >> v;
  198.         --u; --v;
  199.         rlinks[v].emplace_back(u);
  200.         flinks[u].emplace_back(v);
  201.     }
  202.  
  203.     size_t k;
  204.     ist >> k;
  205.     vector_size_t p(k);
  206.     for (size_t i = 0; i < k; i++) {
  207.         ist >> p[i];
  208.         --p[i];
  209.     }
  210.  
  211.     const size_t end = p[p.size() - 1];
  212.  
  213.     vector_size_t distances(n);
  214.     Wave(rlinks, end, distances);
  215.  
  216.     vector_size_t isAmbigous(n);
  217.     for (size_t i = 0; i < n; i++) {
  218.         isAmbigous[i] = IsAmbigous(flinks, i, distances);
  219.     }
  220.     isAmbigous[end] = 0;
  221.  
  222.     size_t minCount = 0;
  223.     size_t maxCount = 0;
  224.     for (size_t i = 0; i < k; i++) {
  225.         const size_t v = p[i];
  226.         const size_t currMinDistance = distances[v];
  227.  
  228.         bool canRebuild = false;
  229.         bool mustRebuild = false;
  230.         if (isAmbigous[v]) {
  231.             canRebuild = true;
  232.         } else if (i + 1 < k) {
  233.             const size_t nextMinDistance = distances[p[i + 1]];
  234.             if (nextMinDistance >= currMinDistance) {
  235.                 canRebuild = true;
  236.                 mustRebuild = true;
  237.             }
  238.         }
  239.         if (canRebuild) {
  240.             maxCount += 1;
  241.         }
  242.         if (mustRebuild) {
  243.             minCount += 1;
  244.         }
  245.     }
  246.     ost << minCount << " " << maxCount << Endl;
  247.     LOCAL_ASSERT(minCount <= maxCount);
  248.  
  249.     return multipleTestMode;
  250. }
  251.  
  252.  
  253. #if LOCAL_TEST
  254. void Test()
  255. {
  256.     using namespace library::random;
  257.     //const auto genVector = GenFactory::CreateGenVector(GenRange<size_t>(2, 10), GenRange<int32_t>(-100, +200));
  258.  
  259.     for (size_t t = 0; t < 10; t++)
  260.     {
  261.         //const vector_int32_t data = genVector();
  262.         //size_t ans = GetAns(data);
  263.         //size_t ref = GetAnsRef(data);
  264.         //LOCAL_ASSERT_EQ(ref, ans);
  265.     }
  266. }
  267. #endif
  268.  
  269. void RunSolve(std::istream& ist, std::ostream& ost)
  270. {
  271. #if !defined(ONLINE_JUDGE)
  272.     while(Solve(ist, ost, true)) {};
  273. #else
  274.     Solve(ist, ost, false);
  275. #endif
  276. }
  277.  
  278. int main(int argc, const char *argv[])
  279. {
  280. #if !defined(ONLINE_JUDGE)
  281.     Test();
  282. #endif
  283.  
  284.     std::ios_base::sync_with_stdio(false);
  285.     if (argc > 1)
  286.     {
  287.         std::ifstream ifs(argv[1]);
  288.         if (!ifs)
  289.         {
  290.             std::cout << "File not found: " << argv[1] << Endl;
  291.             return 1;
  292.         }
  293.         RunSolve(ifs, std::cout);
  294.         return 0;
  295.     }
  296.  
  297.     RunSolve(std::cin, std::cout);
  298. }
RAW Paste Data