SHARE
TWEET

Untitled

a guest Oct 21st, 2018 165 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cmath>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <string>
  6. #include <set>
  7. #include <map>
  8. #include <list>
  9. #include <time.h>
  10. #include <math.h>
  11. #include <random>
  12. #include <deque>
  13. #include <queue>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. #include <iomanip>
  18. #include <bitset>
  19. #include <sstream>
  20. #include <chrono>
  21.  
  22. using namespace std;
  23.  
  24. typedef long long ll;
  25.  
  26. mt19937 rnd(219);
  27.  
  28. struct edge
  29. {
  30.     int a, b;
  31. };
  32.  
  33. const int N = 1e6 + 7;
  34.  
  35. vector <int> g[N];
  36. int col[N];
  37. vector <edge> glob_edges;
  38. bool vis[N];
  39. bool us[N];
  40. int pp;
  41.  
  42. void dfs(int v)
  43. {
  44.     us[v] = true;
  45.     while (g[v].size() > 0)
  46.     {
  47.         int ind = g[v].back();
  48.         g[v].pop_back();
  49.         if (vis[ind])
  50.         {
  51.             continue;
  52.         }
  53.         vis[ind] = true;
  54.         col[ind] = (pp ^= 1);
  55.         dfs(glob_edges[ind].a == v ? glob_edges[ind].b : glob_edges[ind].a);
  56.     }
  57. }
  58.  
  59. vector <int> solve(vector <edge> e)
  60. {
  61.     if (e.empty())
  62.     {
  63.         return {};
  64.     }
  65.     vector <int> l, r;
  66.     for (auto c : e)
  67.     {
  68.         l.push_back(c.a);
  69.         r.push_back(c.b);
  70.     }
  71.     sort(l.begin(), l.end());
  72.     sort(r.begin(), r.end());
  73.     l.resize(unique(l.begin(), l.end()) - l.begin());
  74.     r.resize(unique(r.begin(), r.end()) - r.begin());
  75.     glob_edges.clear();
  76.     int x = (int) l.size() + 1, y = (int) r.size() + 1;
  77.     for (int i = 0; i < x + y; i++) g[i].clear();
  78.     int ind = 0;
  79.     for (auto &c : e)
  80.     {
  81.         c.a = lower_bound(l.begin(), l.end(), c.a) - l.begin();
  82.         c.b = lower_bound(r.begin(), r.end(), c.b) - r.begin();
  83.         auto ret = c;
  84.         ret.b += x;
  85.         glob_edges.push_back(ret);
  86.         g[ret.a].push_back(ind);
  87.         g[ret.b].push_back(ind);
  88.         ind++;
  89.     }
  90.     vector <int> ids;
  91.     int mx = 0;
  92.     for (int i = 0; i < x + y; i++)
  93.     {
  94.         us[i] = 0;
  95.         mx = max(mx, (int) g[i].size());
  96.         if (g[i].size() % 2)
  97.         {
  98.             ids.push_back(i);
  99.         }
  100.     }
  101.     bool bad = false;
  102.     for (int i = 0; i < x + y; i++)
  103.     {
  104.         if (g[i].size() > 1)
  105.         {
  106.             bad = true;
  107.         }
  108.     }
  109.     if (!bad)
  110.     {
  111.         vector <int> res(ind);
  112.         return res;
  113.     }
  114.     else
  115.     {
  116.         vector <int> deg(x + y);
  117.         for (int v : ids)
  118.         {
  119.             if (v < x)
  120.             {
  121.                 glob_edges.push_back({v, x + y - 1});
  122.                 g[v].push_back(ind);
  123.                 g[x + y - 1].push_back(ind);
  124.                 ind++;
  125.             }
  126.             else
  127.             {
  128.                 glob_edges.push_back({v, x - 1});
  129.                 g[v].push_back(ind);
  130.                 g[x - 1].push_back(ind);
  131.                 ind++;
  132.             }
  133.         }
  134.         if (g[x - 1].size() % 2)
  135.         {
  136.             glob_edges.push_back({x - 1, x + y - 1});
  137.             g[x - 1].push_back(ind);
  138.             g[x + y - 1].push_back(ind);
  139.             ind++;
  140.         }
  141.         for (int i = 0; i < ind; i++)
  142.         {
  143.             col[i] = -1;
  144.         }
  145.         for (int i = 0; i < ind; i++)
  146.         {
  147.             vis[i] = 0;
  148.         }
  149.         for (int i = 0; i < x + y; i++)
  150.         {
  151.             if (!g[i].empty())
  152.             {
  153.                 dfs(i);
  154.             }
  155.         }
  156.         vector <edge> to_l, to_r;
  157.         vector <int> cols;
  158.         for (int i = 0; i < (int) e.size(); i++)
  159.         {
  160.             cols.push_back(col[i]);
  161.             if (col[i] == 0)
  162.             {
  163.                 to_l.push_back(e[i]);
  164.             }
  165.             else
  166.             {
  167.                 to_r.push_back(e[i]);
  168.             }
  169.         }
  170.         auto x = solve(to_l);
  171.         auto y = solve(to_r);
  172.         int mx = *max_element(x.begin(), x.end()) + 1;
  173.         int p_x = 0, p_y = 0;
  174.         vector <int> ans;
  175.         for (int i = 0; i < (int) e.size(); i++)
  176.         {
  177.             if (cols[i] == 0)
  178.             {
  179.                 ans.push_back(x[p_x++]);
  180.             }
  181.             else
  182.             {
  183.                 ans.push_back(mx + y[p_y++]);
  184.             }
  185.         }
  186.         return ans;
  187.     }
  188. }
  189.  
  190. set <int> a[N];
  191.  
  192. int main()
  193. {
  194. #ifdef ONPC
  195.     freopen("a.in", "r", stdin);
  196. #endif
  197.     ios::sync_with_stdio(0);
  198.     cin.tie(0);
  199. #ifdef ONPC
  200.     while (true)
  201.     {
  202.         vector <edge> e;
  203.         int l = rnd() % 100 + 1, r = rnd() % 100 + 1, m = rnd() % (l * r) + 1;
  204.         //int l = 100000, r = 100000, m = 500000;
  205.         set <pair <int, int> > q;
  206.         for (int i = 0; i < m; i++)
  207.         {
  208.             int a = rnd() % l + 1, b = rnd() % r + 1;
  209.             while (q.count({a, b}))
  210.             {
  211.                 a = rnd() % l + 1;
  212.                 b = rnd() % r + 1;
  213.             }
  214.             q.insert({a, b});
  215.             a--, b--;
  216.             e.push_back({a, b});
  217.         }
  218.         for (int i = 0; i < l + r; i++) a[i].clear();
  219.         auto ret = solve(e);
  220.         int mx = 0;
  221.         for (int i = 0; i < m; i++)
  222.         {
  223.             assert(!a[e[i].a].count(ret[i]));
  224.             assert(!a[l + e[i].b].count(ret[i]));
  225.             a[e[i].a].insert(ret[i]);
  226.             a[l + e[i].b].insert(ret[i]);
  227.             mx = max(mx, (int) a[e[i].a].size());
  228.             mx = max(mx, (int) a[l + e[i].b].size());
  229.         }
  230.         int cur = 1;
  231.         while (cur < mx)
  232.         {
  233.             cur *= 2;
  234.         }
  235.         cout << *max_element(ret.begin(), ret.end()) + 1 << ' ' << cur << ' ' << mx << endl;
  236.         assert(*max_element(ret.begin(), ret.end()) + 1 <= cur);
  237.         cout << "OK" << endl;
  238.         return 0;
  239.     }
  240. #else
  241.     vector <edge> e;
  242.     int l, r, m;
  243.     cin >> l >> r >> m;
  244.     for (int i = 0; i < m; i++)
  245.     {
  246.         int a, b;
  247.         cin >> a >> b;
  248.         a--, b--;
  249.         e.push_back({a, b});
  250.     }
  251.     auto ret = solve(e);
  252.     cout << *max_element(ret.begin(), ret.end()) + 1 << '\n';
  253.     for (int c : ret)
  254.     {
  255.         cout << c + 1 << '\n';
  256.     }
  257. #endif
  258. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top