1695.md (6309B)
1 Source: https://codeforces.com/blog/entry/103996 2 3 Tutorial is loading... 4 5 **Solution** 6 7 ``` 8 #include <bits/stdc++.h> 9 using namespace std; 10 11 int grid[45][45]; 12 13 int main() { 14 int num_tests; 15 cin >> num_tests; 16 17 for (int test = 0; test < num_tests; ++test) { 18 int n, m; 19 cin >> n >> m; 20 21 int max_i = 0, max_j = 0; 22 23 for (int i = 0; i < n; ++i) 24 for (int j = 0; j < m; ++j) { 25 cin >> grid[i][j]; 26 if (grid[i][j] > grid[max_i][max_j]) 27 max_i = i, max_j = j; 28 } 29 30 int h = max(max_i+1, n-max_i); 31 int w = max(max_j+1, m-max_j); 32 cout << h * w << '\n'; 33 } 34 } 35 ``` 36 37 Tutorial is loading... 38 39 **Solution** 40 41 ``` 42 #include <bits/stdc++.h> 43 using namespace std; 44 45 int main() { 46 int num_tests; 47 cin >> num_tests; 48 49 for (int test = 0; test < num_tests; ++test) { 50 51 int n; cin >> n; 52 vector<int> a(n); 53 for (int i = 0; i < n; ++i) 54 cin >> a[i]; 55 56 if (n % 2 == 1) { 57 cout << "Mike\n"; 58 continue; 59 } 60 61 int smallest = 0; 62 for (int i = 0; i < n; ++i) 63 if (a[i] < a[smallest]) 64 smallest = i; 65 66 if (smallest % 2 == 0) cout << "Joe\n"; 67 else cout << "Mike\n"; 68 } 69 } 70 ``` 71 72 Tutorial is loading... 73 74 **Solution** 75 76 ``` 77 #include <bits/stdc++.h> 78 using namespace std; 79 80 #define N 1010 81 82 int grid[N][N], mn[N][N], mx[N][N]; 83 84 int main() { 85 int num_tests; 86 cin >> num_tests; 87 88 for (int test = 0; test < num_tests; ++test) { 89 int n, m; 90 cin >> n >> m; 91 92 for(int i = 0; i < n; ++i) 93 for(int j = 0; j < m; ++j) 94 cin >> grid[i][j]; 95 96 mn[0][0] = mx[0][0] = grid[0][0]; 97 98 for(int i = 1; i < n; ++i) 99 mx[i][0] = mn[i][0] = mx[i - 1][0] + grid[i][0]; 100 101 for(int j = 1; j < m; ++j) 102 mx[0][j] = mn[0][j] = mx[0][j - 1] + grid[0][j]; 103 104 for(int i = 1; i < n; ++i) 105 for(int j = 1; j < m; ++j) { 106 mx[i][j] = max(mx[i - 1][j], mx[i][j - 1]) + grid[i][j]; 107 mn[i][j] = min(mn[i - 1][j], mn[i][j - 1]) + grid[i][j]; 108 } 109 110 if(mx[n - 1][m - 1] % 2 || mn[n - 1][m - 1] > 0 || mx[n - 1][m - 1] < 0) 111 cout << "NO\n"; 112 else 113 cout << "YES\n"; 114 } 115 } 116 ``` 117 118 Tutorial is loading... 119 120 **Solution** 121 122 ``` 123 #include <bits/stdc++.h> 124 using namespace std; 125 126 #define N 2010 127 128 vector<int> tree[N]; 129 130 int dfs(int i, int p) { 131 int sm = 0, z = 0; 132 133 for (int j : tree[i]) if (j != p) { 134 int x = dfs(j, i); 135 sm += x; 136 if (x == 0) 137 z++; 138 } 139 140 return sm + max(0, z - 1); 141 } 142 143 int main() { 144 int num_tests; 145 cin >> num_tests; 146 147 for (int test = 0; test < num_tests; ++test) { 148 int n; 149 cin >> n; 150 151 for (int i = 1; i < n; ++i) { 152 int u, v; 153 cin >> u >> v; 154 tree[u].push_back(v); 155 tree[v].push_back(u); 156 } 157 158 if (n == 1) 159 cout << "0\n"; 160 else { 161 int ans = n; 162 163 for (int i = 1; i <= n; ++i) 164 ans = min(ans, 1 + dfs(i, i)); 165 166 cout << ans << '\n'; 167 } 168 169 for (int i = 1; i <= n; ++i) 170 tree[i].clear(); 171 } 172 } 173 ``` 174 175 Tutorial is loading... 176 177 **Solution** 178 179 ``` 180 #include <bits/stdc++.h> 181 using namespace std; 182 183 #define N 200010 184 185 vector<int> tree[N]; 186 187 int dfs(int i, int p) { 188 int sm = 0, z = 0; 189 190 for (int j : tree[i]) if (j != p) { 191 int x = dfs(j, i); 192 sm += x; 193 if (x == 0) 194 z++; 195 } 196 197 return sm + max(0, z - 1); 198 } 199 200 int main() { 201 int num_tests; 202 cin >> num_tests; 203 204 for (int test = 0; test < num_tests; ++test) { 205 int n; 206 cin >> n; 207 208 for (int i = 1; i < n; ++i) { 209 int u, v; 210 cin >> u >> v; 211 tree[u].push_back(v); 212 tree[v].push_back(u); 213 } 214 215 int max_deg = 0; 216 for (int i = 1; i <= n; ++i) 217 max_deg = max(max_deg, (int)tree[i].size()); 218 219 if (max_deg == 0) 220 cout << "0\n"; 221 else if (max_deg < 3) 222 cout << "1\n"; 223 else { 224 for (int i = 1; i <= n; ++i) 225 if (tree[i].size() >= 3) { 226 cout << dfs(i, i) << '\n'; 227 break; 228 } 229 } 230 231 for (int i = 1; i <= n; ++i) 232 tree[i].clear(); 233 } 234 } 235 ``` 236 237 Tutorial is loading... 238 239 **Solution** 240 241 ``` 242 #include <bits/stdc++.h> 243 using namespace std; 244 245 #define N 600010 246 247 vector<pair<int, int>> graph[N]; 248 vector<int> lst; 249 250 int ans[2][N]; 251 252 bool used[N], usedEdges[N]; 253 254 void dfs(int i) { 255 lst.push_back(i); 256 257 if (!used[i]) { 258 used[i] = true; 259 260 for (pair<int, int> p : graph[i]) 261 if (!usedEdges[p.second]) { 262 usedEdges[p.second] = true; 263 dfs(p.first); 264 lst.push_back(i); 265 } 266 } 267 } 268 269 int main() { 270 271 int n; cin >> n; 272 string ptop(n, 'U'), pbot(n, 'D'); 273 string mtop(n, 'U'), mbot(n, 'D'); 274 275 for (int i = 0; i < n; ++i) { 276 int u, v; 277 cin >> u >> v; 278 graph[u].emplace_back(v, i); 279 graph[v].emplace_back(u, i); 280 } 281 282 int idx = 0; 283 for (int i = 1; i <= 2 * n; ++i) if (!used[i]) { 284 285 dfs(i); 286 lst.pop_back(); 287 int k = lst.size() / 2; 288 289 if (k == 1) { 290 cout << "-1\n"; 291 exit(0); 292 } 293 294 for (int j = 0; j < k; ++j) { 295 ans[0][j + idx] = lst[j]; 296 ans[1][j + idx] = lst[2 * k - 1 - j]; 297 } 298 299 for (int j = 0; j < k - 1; j += 2) 300 ptop[j + idx] = pbot[j + idx] = 'L', ptop[j + 1 + idx] = pbot[j + 1 + idx] = 'R'; 301 for (int j = 1; j < k - 1; j += 2) 302 mtop[j + idx] = mbot[j + idx] = 'L', mtop[j + 1 + idx] = mbot[j + 1 + idx] = 'R'; 303 lst.clear(); 304 305 idx += k; 306 } 307 308 cout << "2 " << n << '\n'; 309 310 for (int i = 0; i < 2; ++i) { 311 for (int j = 0; j < n; ++j) 312 cout << ans[i][j] << ' '; 313 cout << '\n'; 314 } 315 316 cout << ptop << '\n' << pbot << '\n'; 317 cout << mtop << '\n' << mbot << '\n'; 318 } 319 ```