제출 #274741

#제출 시각아이디문제언어결과실행 시간메모리
274741Haunted_Cpp자리 배치 (IOI18_seats)C++17
0 / 100
4061 ms59492 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; class DisjointSet{ private: vector<int> size; vector<int> parent; vector<int> min_row; vector<int> max_row; vector<int> min_column; vector<int> max_column; public: DisjointSet(int H, int W) { size = parent = min_row = max_row = min_column = max_column = vector<int>(H * W + 25); for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { int idx = i * W + j; size[idx] = 1; parent[idx] = idx; min_row[idx] = max_row[idx] = i; min_column[idx] = max_column[idx] = j; } } } int root(int x) { while(x != parent[x]) x = parent[x]; return x; } void join(int a, int b) { a = root(a); b = root(b); if (a == b) return; if (size[a] < size[b]) swap(a, b); size[a] += size[b]; max_row[a] = max(max_row[a], max_row[b]); min_row[a] = min(min_row[a], min_row[b]); max_column[a] = max(max_column[a], max_column[b]); min_column[a] = min(min_column[a], min_column[b]); parent[b] = a; } int is_cute(int idx, int tamanho_total) { const int s = root(idx); if(size[s] != tamanho_total) return 0; const int rec = (max_row[s] - min_row[s] + 1) * (max_column[s] - min_column[s] + 1); return rec == tamanho_total; } }; int r, c; vector<pair<int, int>> where; vector<vector<int>> mat; void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { r = H; c = W; where.resize(r * c); mat = vector<vector<int>>(r, vector<int>(c)); for (int i = 0; i < r * c; i++) { where[i] = {R[i], C[i]}; mat[R[i]][C[i]] = i; } } const int dr[] = {+1, -1, +0, +0}; const int dc[] = {+0, +0, +1, -1}; int solve() { DisjointSet DSU(r, c); int res = 0; const int sr = where[0].first; const int sc = where[0].second; for (int i = 0; i < r * c; i++) { const int linha = where[i].first; const int coluna = where[i].second; for (int x = 0; x < 4; x++) { if (linha + dr[x] < 0 || linha + dr[x] >= r || coluna + dc[x] < 0 || coluna + dc[x] >= c) continue; if (mat[linha + dr[x]][coluna + dc[x]] >= i) continue; DSU.join(linha * c + coluna, (linha + dr[x]) * c + coluna + dc[x]); } res += DSU.is_cute(sr * r + sc, i + 1); } return res; } int swap_seats(int a, int b) { swap(mat[where[a].first][where[a].second], mat[where[b].first][where[b].second]); swap(where[a], where[b]); return solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...