fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifdef LOCAL
  5. #define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__)
  6. #else
  7. #define DEBUG(...) 6
  8. #endif
  9.  
  10. template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
  11. template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
  12. ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
  13. template<typename T> void debug(string s, T x) {cerr << "\033[1;35m" << s << "\033[0;32m = \033[33m" << x << "\033[0m\n";}
  14. template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
  15. if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << "\033[1;35m" << s.substr(0, i) << "\033[0;32m = \033[33m" << x << "\033[31m | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}
  16.  
  17. int main() {
  18. ios_base::sync_with_stdio(false);
  19. cin.tie(NULL);
  20.  
  21. int n;
  22. cin >> n;
  23. vector<array<int, 2>> trie(1);
  24. vector<int> cnt(1);
  25. for (int i=0; i<n; i++) {
  26. string s;
  27. cin >> s;
  28.  
  29. uint32_t val = 0;
  30. int last = 0;
  31. for (int j=0; j<(int)s.size(); j++)
  32. if (s[j] == '.' || s[j] == '/') {
  33. val = (val << 8) + stoi(s.substr(last, j - last));
  34. last = j + 1;
  35. }
  36. int u = 0, len = stoi(s.substr(s.find('/') + 1));
  37. for (int j=31; j>=0 && len>0; j--, len--) {
  38. int b = val >> j & 1;
  39. if (!trie[u][b]) {
  40. trie[u][b] = (int) trie.size();
  41. trie.emplace_back();
  42. cnt.emplace_back();
  43. }
  44. u = trie[u][b];
  45. }
  46. cnt[u]++;
  47. }
  48.  
  49. auto dfs1 = [&] (auto &self, int u, int len, uint32_t val) -> void {
  50. if (u == 0 && len > 0)
  51. return;
  52. self(self, trie[u][0], len + 1, val << 1);
  53. self(self, trie[u][1], len + 1, (val << 1) + 1);
  54. if (cnt[trie[u][0]] > 0 && cnt[trie[u][1]] > 0)
  55. cnt[u]++;
  56. };
  57.  
  58. auto dfs2 = [&] (auto &self, int u, int len, uint32_t val) -> void {
  59. if (u == 0 && len > 0)
  60. return;
  61. if (cnt[u] > 0) {
  62. uint32_t cur = val << (32 - len);
  63. string ret = '/' + to_string(len);
  64. for (int rep=0; rep<4; rep++) {
  65. ret = '.' + to_string(cur % 256) + ret;
  66. cur >>= 8;
  67. }
  68. cout << ret.substr(1) << "\n";
  69. return;
  70. }
  71. self(self, trie[u][0], len + 1, val << 1);
  72. self(self, trie[u][1], len + 1, (val << 1) + 1);
  73. };
  74.  
  75. dfs1(dfs1, 0, 0, 0);
  76. dfs2(dfs2, 0, 0, 0);
  77.  
  78. return 0;
  79. }
  80.  
Runtime error #stdin #stdout #stderr 0.01s 5292KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
terminate called after throwing an instance of 'std::invalid_argument'
  what():  stoi