Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Mar 29th, 2020 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma GCC optimize("O3")
  2. #pragma GCC target("avx2")
  3. #include <iostream>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <bitset>
  7. #include <set>
  8. #include <map>
  9. #include <string>
  10. #include <cmath>
  11. #include <queue>
  12. #include <ctime>
  13.  
  14. using namespace std;
  15.  
  16. typedef long long ll;
  17. typedef long double ld;
  18. #define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  19. const ll SIZE= 1e5 * 3 + 10, INF = 1e9 * 1e9 + 2, MOD = 1e9 + 7;
  20.  
  21. vector<vector<ll>> graph;
  22. ll q;
  23. vector<ll> vec;
  24. bool used[SIZE];
  25.  
  26. struct edge {
  27.     int c, bal, ind, to, fr = -1;
  28. };
  29.  
  30. vector<edge> edges;
  31.  
  32. int n, m, nd;
  33. int dfs(int v, int curMin = INT32_MAX) {
  34.     used[v] = true;
  35.     if (v == nd) {
  36.         return curMin;
  37.     }
  38.  
  39.     for (auto to : graph[v]) {
  40.         if (edges[to].bal > 0 && !used[edges[to].to]) {
  41.             int val = dfs(edges[to].to, min(curMin, edges[to].bal));
  42.             if (val > 0) {
  43.                 curMin = min(val, curMin);
  44.                 edges[to].bal -= curMin;
  45.                 edges[to ^ 1].bal += curMin;
  46.                 return curMin;
  47.             }
  48.         }
  49.     }
  50.  
  51.     return 0;
  52. }
  53.  
  54. int main() {
  55.     cin >> n >> m;
  56.    
  57.     nd = n + m + 1;
  58.     graph.resize(n + m + 2);
  59.     for (int i = 1; i <= n; i++) {
  60.         int q;
  61.         cin >> q;
  62.         while (q != 0) {
  63.             q += n;
  64.             edges.push_back({ 1, 1, int(edges.size() - 1), q , i});
  65.             edges.push_back({ 0, 0, int(edges.size() - 1), i});
  66.             graph[i].push_back(edges.size() - 2);
  67.             graph[q].push_back(edges.size() - 1);
  68.             cin >> q;
  69.         }
  70.     }
  71.  
  72.     for (int i = 1; i <= n; i++) {
  73.         edges.push_back({ 1, 1, int(edges.size() - 1), i });
  74.         edges.push_back({ 0, 0, int(edges.size() - 1), 0 });
  75.         graph[0].push_back(edges.size() - 2);
  76.         graph[i].push_back(edges.size() - 1);
  77.     }
  78.     for (int i = n + 1; i <= n + m; i++) {
  79.         edges.push_back({ 1, 1, int(edges.size() - 1), nd });
  80.         edges.push_back({ 0, 0, int(edges.size() - 1), i });
  81.         graph[i].push_back(edges.size() - 2);
  82.         graph[nd].push_back(edges.size() - 1);
  83.     }
  84.  
  85.     ll q = dfs(0);
  86.     while (q != 0) {
  87.         for (int i = 0; i <= nd; i++) used[i] = false;
  88.         q = dfs(0);
  89.     }
  90.  
  91.     vector<pair<ll, ll>> ans;
  92.     for (int i = 0; i < edges.size(); i++) {
  93.         if (edges[i].fr != -1 && edges[i].bal == 0) ans.push_back({ edges[i].fr, edges[i].to - n });
  94.     }
  95.     cout << ans.size() << "\n";
  96.     for (int i = 0; i < ans.size(); i++) {
  97.         cout << ans[i].first << " " << ans[i].second << "\n";
  98.     }
  99.     return 0;
  100. }
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