Advertisement
TrickmanOff

Untitled

Feb 25th, 2020
261
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.02 KB | None | 0 0
  1. #pragma GCC optimize("Ofast,no-stack-protector")
  2. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  3. #pragma GCC optimize("unroll-loops", "fast-math")
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <fstream>
  7. #include <vector>
  8. #include <queue>
  9. #include <functional>
  10. #include <set>
  11. #include <map>
  12. #include <math.h>
  13. #include <cmath>
  14. #include <string>
  15. #include <random>
  16. #include <unordered_set>
  17. #include <unordered_map>
  18. #include <bitset>
  19. #include <string.h>
  20. #include <stack>
  21. #include <assert.h>
  22. #include <list>
  23. using namespace std;
  24. //
  25. #define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
  26. #define cin in
  27. #define cout out
  28. #define ll long long
  29. #define db double
  30. #define ld long double
  31. #define uset unordered_set
  32. #define umap unordered_map
  33. #define F first
  34. #define S second
  35. #define ms multiset
  36. #define pb push_back
  37. #define pq priority_queue
  38. #define umap unordered_map
  39. #define uset unordered_set
  40. #define pii pair<int, int>
  41. #define pll pair<ll, ll>
  42. #define pdd pair<ld, ld>
  43. #define pnn pair<Node*, Node*>
  44. #define uid uniform_int_distribution
  45. #define PI acos(-1.0)
  46.  
  47. ifstream in("input.txt");
  48. ofstream out("output.txt");
  49.  
  50. const int MAX_N = 1000, MAX_V = MAX_N * MAX_N;
  51.  
  52. vector<int> tg[MAX_V];
  53. int g[MAX_V], act[MAX_V], add[MAX_V];
  54. bool bot[MAX_V], used[MAX_V];
  55. int n, m, G;
  56.  
  57. int pos(int i, int j) {
  58. return i * m + j;
  59. }
  60.  
  61. void input() {
  62. cin >> n >> m >> G;
  63. for (int i = 0; i < n; i++) {
  64. string s;
  65. cin >> s;
  66. for (int j = 0; j < m; j++) {
  67. int v = pos(i, j);
  68. if (s[j] == 'N' || s[j] == 'n')
  69. g[v] = (pos(i - 1, j));
  70. else if (s[j] == 'E' || s[j] == 'e')
  71. g[v] = (pos(i, j + 1));
  72. else if (s[j] == 'S' || s[j] == 's')
  73. g[v] = (pos(i + 1, j));
  74. else
  75. g[v] = (pos(i, j - 1));
  76.  
  77. if (s[j] == 'N' || s[j] == 'E' || s[j] == 'S' || s[j] == 'W')
  78. bot[v] = 1;
  79. }
  80. }
  81. n *= m;
  82. for (int v = 0; v < n; v++)
  83. tg[g[v]].push_back(v);
  84. }
  85.  
  86. bool cur_used[MAX_V];
  87. void find_cyc(int v, vector<int>& cyc) {
  88. stack<int> st;
  89. while (!cur_used[v]) {
  90. st.push(v);
  91. cur_used[v] = 1;
  92. v = g[v];
  93. }
  94.  
  95. cyc.push_back(v);
  96. while (st.top() != v) {
  97. cyc.push_back(st.top());
  98. st.pop();
  99. }
  100. reverse(cyc.begin(), cyc.end());
  101. }
  102.  
  103. int ans = 0;
  104. int T = 0;
  105.  
  106. struct tr {
  107. int k, t, v;
  108. };
  109.  
  110. /*
  111. хочу знать минимальное время, для которого можно выстроить
  112. не более K роботов в "очередь" на выход из поддерева
  113. и время, в которое их нужно активировать
  114. */
  115.  
  116. tr q(int v, int K) {
  117.  
  118. }
  119.  
  120. void solve(int v) {
  121. vector<int> cyc;
  122. find_cyc(v, cyc);
  123.  
  124. int bot_cyc = 0;
  125. {
  126. bool fl = 0;
  127. for (int x : cyc) {
  128. if (bot[x]) {
  129. act[x] = T;
  130. fl = 1;
  131. bot_cyc++;
  132. }
  133. else if (fl)
  134. T++;
  135. }
  136. }
  137.  
  138. int k = cyc.size() - bot_cyc;
  139.  
  140. }
  141.  
  142. int main() {
  143. fast;
  144. input();
  145. memset(act, 255, sizeof(act));
  146.  
  147. for (int v = 0; v < n; v++) {
  148. if(!used[v])
  149. solve(v);
  150. }
  151.  
  152. cout << ans;
  153. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement