fork download 
  1. /**
  2.  *    author:  orzvanh14 ( Độc cô cầu đặc )
  3.  *    created: 18.04.2026 03:56:02
  4.  *    too lazy to update time
  5. **/
  6. // i wants to take ioi
  7. //binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13. #define nn "\n"
  14. #define pi pair<int, int>
  15. #define ti tuple<int, int, int>
  16. #define fi first
  17. #define se second
  18. #define lb lower_bound
  19. #define ub upper_bound
  20. #define eb emplace_back
  21. #define pb push_back
  22. #define TASK " "
  23.  
  24. #define ms(a, x) memset(a, x, sizeof(a))
  25. #define all(a) a.begin(), a.end()
  26. #define All(a, n) a + 1, a + 1 + n
  27.  
  28. #define LOG 19
  29.  
  30. const int INF = 1e18;
  31. const int N = 1e2 + 5;
  32. const int maxn = 100 + 5;
  33. const int mod = 1e9 + 7;
  34.  
  35.  
  36. struct node{
  37. 	int kc, u;
  38. 	bool operator<(const node& other) const {
  39.         return kc > other.kc;
  40.     }
  41. };
  42. struct edge{
  43. 	int u, v, w;
  44. };
  45. int n, m;
  46. int sz[N][N];
  47. pi par[N][N];
  48. int dx[] = {0, 0 , -1, 1};
  49. int dy[] = {1, -1, 0, 0};
  50. struct kq{
  51.     int u1, v1, u2, v2;
  52. };
  53. vector<kq> ans;
  54. void make_sets(int s, int y){
  55.     sz[s][y] = 1;
  56.     par[s][y] = {s, y};
  57. }
  58. pi get(int a, int A){
  59.     if(make_pair(a, A) == par[a][A]) return {a, A};
  60.     return par[a][A] = get(par[a][A].fi, par[a][A].se);
  61. }
  62. void union_sets(int a, int A, int b, int B){
  63.     auto [ra, rA] = get(a, A);
  64.     auto [rb, rB] = get(b, B);
  65.     if(ra != rb || rA != rB){
  66.         if(sz[ra][rA] < sz[rb][rB]){
  67.             // sz[a] > sz[b]
  68.             swap(ra, rb);
  69.             swap(rA, rB);
  70.         }
  71.         sz[ra][rA] += sz[rb][rB];
  72.         par[rb][rB] = {ra, rA};
  73.     }
  74. }
  75. void nhap(){
  76. 	cin >> m >> n;
  77. 	for(int i = 0; i <= m; i++){
  78.         for(int j = 0; j <= n; j++){
  79.             make_sets(i, j);
  80.         }
  81. 	}
  82. 	int x1, y1, x2, y2;
  83. 	while(cin >> x1 >> y1 >> x2 >> y2){
  84.         union_sets(x1, y1, x2, y2);
  85. 	}
  86.  
  87. }
  88. void solve(){
  89. 	for(int i = 0; i <= m; i++){
  90.         for(int j = 0; j <= n; j++){
  91.             auto [u, v] = get(i, j);
  92.             for(int k = 0; k < 4; k++){
  93.                 int x = i + dx[k];
  94.                 int y = j + dy[k];
  95.                 if(x <= m && y <= n && x >= 0 && y >= 0){
  96.                     auto [U, V] = get(x, y);
  97.                     if(u != U || v  != V){
  98.                         union_sets(u, v, x, y);
  99.                         ans.pb({i, j, x, y});
  100.                     }
  101.                 }
  102.             }
  103.         }
  104. 	}
  105. 	cout << ans.size() << nn;
  106. 	for(int i = 0; i < ans.size(); i++){
  107.         cout << ans[i].u1 << " " << ans[i].v1 << " " << ans[i].u2 << " " << ans[i].v2 << nn;
  108. 	}
  109. }
  110. signed main(){
  111. 	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  112. 	nhap();
  113. 	solve();
  114. 	return 0;
  115. }
  116.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
2 3
0 0 1 0
1 0 2 0
1 0 1 1
2 0 2 1
0 1 1 1
1 1 2 1
1 2 2 2
0 3 1 3
stdout 
4
0 1 0 2
0 2 0 3
0 2 1 2
1 3 2 3
https://ideone.com/1OaCbB
language:
C++14 (gcc 8.3)
created:
11 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!