Hướng dẫn cho LQDOJ CUP 2022 - Round 1 - COLORING
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Subtask \(1\) (\(25\%\) số điểm): \(n \le 10\).
Tutorial
Thử mọi cách tô màu cây và tìm ra dãy có thứ tự từ điển nhỏ nhất. Cần cài đặt khéo léo để tránh code quá dài và độ phức tạp quá lớn.
Độ phức tạp: \(\displaystyle \mathcal{O} \left( \frac{n! \cdot n^2}{2^{\frac{n}{2}}} \right)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 500005;
int numNode;
vector<int> adj[MAX_N];
int par[MAX_N], dep[MAX_N];
vector<int> answer, current;
void dfs(int node) {
for (auto u : adj[node]) {
if (u != par[node]) {
par[u] = node;
dep[u] = dep[node] + 1;
dfs(u);
}
}
}
vector<int> get_path(int s, int t) {
vector<int> lef, rig;
while (dep[s] > dep[t]) {
lef.push_back(s);
s = par[s];
}
while (dep[t] > dep[s]) {
rig.push_back(t);
t = par[t];
}
while (s != t) {
lef.push_back(s);
rig.push_back(t);
s = par[s];
t = par[t];
}
lef.push_back(s);
lef.insert(lef.end(), rig.begin(), rig.end());
sort(lef.begin(), lef.end());
return lef;
}
void solve(vector<int> idx, int clr) {
if (idx.empty()) {
answer = min(answer, current);
return;
}
for (int i = 0; i < (int)idx.size(); i++) {
for (int j = i + ((int)idx.size() == numNode); j < (int)idx.size(); j++) {
vector<int> path = get_path(idx[i], idx[j]);
bool chk = true;
for (auto u : path) {
chk &= !current[u];
}
if (!chk) {
continue;
}
for (auto u : path) {
current[u] = clr;
}
vector<int> new_idx;
for (int k = 0; k < (int)idx.size(); k++) {
if (!binary_search(path.begin(), path.end(), idx[k])) {
new_idx.push_back(idx[k]);
}
}
solve(new_idx, clr + 1);
for (auto u : path) {
current[u] = 0;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> numNode;
for (int i = 1; i <= numNode - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
if (numNode == 1) {
cout << 1 << '\n';
return 0;
}
dfs(1);
vector<int> idx(numNode);
iota(idx.begin(), idx.end(), 1);
answer.resize(numNode + 1);
answer[0] = 1;
current.resize(numNode + 1);
solve(idx, 1);
for (int u = 1; u <= numNode; u++) {
cout << answer[u] << ' ';
}
return 0;
}
Subtask \(2\) (\(25\%\) số điểm): \(n \le 5 \cdot 10 ^ 2\).
Subtask \(3\) (\(25\%\) số điểm): \(n \le 5 \cdot 10 ^ 3\).
Tutorial
Ta sẽ dùng thuật toán tham lam để giải quyết.
Với đỉnh nhỏ nhất chưa được tô màu, ta sẽ tô màu một đường đi chứa đỉnh đó là màu nhỏ nhất chưa được chọn để tô và đồng thời các đỉnh trên đường đi này sau khi sắp xếp sẽ có thứ tự từ điển nhỏ nhất.
Dể làm được điều này, ta có thể cố định đỉnh đó là gốc của cây. Gọi \(idx[u]\) là đỉnh có chỉ số nhỏ nhất trong cây con gốc \(u\). Đầu tiên, ta tìm hai nhánh con của gốc mà có \(idx\) nhỏ nhất. Sau đó đi sâu xuống bằng cách chọn đỉnh tiếp theo có \(idx\) nhỏ nhất là ta đã có được một đường đi thỏa mãn. Sau khi tìm được, ta sẽ tô màu các đỉnh này và "xóa" ra khỏi cây. Khi này, cây sẽ trở thành một rừng cây và ta sẽ có được cách tô màu cho cả cây bằng cách lặp lại thuật toán trên.
Độ phức tạp: Tùy vào cách cài đặt, lời giải này sẽ có độ phức tạp \(\mathcal{O}(n^3)\) hoặc \(\mathcal{O}(n^2)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 500005;
int numNode;
vector<int> adj[MAX_N];
int idx[MAX_N];
bool del[MAX_N];
int ans[MAX_N], cur;
void dfs(int node, int parent) {
idx[node] = node;
for (auto u : adj[node]) {
if (u != parent && !del[u]) {
dfs(u, node);
idx[node] = min(idx[node], idx[u]);
}
}
}
void down(int node, int parent) {
del[node] = true;
ans[node] = cur;
pair<int, int> path = make_pair(INT_MAX, -1);
for (auto u : adj[node]) {
if (u != parent && !del[u]) {
path = min(path, make_pair(idx[u], u));
}
}
if (path.second != -1) {
down(path.second, node);
}
}
void solve(int node) {
dfs(node, 0);
pair<int, int> path_1 = make_pair(INT_MAX, -1), path_2 = make_pair(INT_MAX, -1);
for (auto u : adj[node]) {
if (!del[u]) {
pair<int, int> tmp = make_pair(idx[u], u);
if (path_1 > tmp) {
path_2 = path_1;
path_1 = tmp;
} else if (path_2 > tmp) {
path_2 = tmp;
}
}
}
del[node] = true;
ans[node] = cur;
if (path_1.second != -1) {
down(path_1.second, node); }
if (path_2.second != -1) {
down(path_2.second, node);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> numNode;
for (int i = 1; i <= numNode - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
cur = 0;
for (int u = 1; u <= numNode; u++) {
if (!del[u]) {
cur++;
solve(u);
}
}
for (int u = 1; u <= numNode; u++) {
cout << ans[u] << ' ';
}
cout << '\n';
return 0;
}
Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.
Tutorial
Ta sẽ giải quyết bài toán trên cây con gốc \(u\). Ban đầu, nối các nút nằm trên đường đi giữa nút \(min1\) và \(min2\) (hai nút có giá trị nhỏ nhất trong cây con gốc \(u\)). Sau đấy ta sẽ mở rộng đường đi này cho đến khi không thể nào nối thêm được nữa. Để mở rộng đường đi, ta sẽ làm như sau:
Giả sử hai nút mà đường đi của chúng đã được nối với nhau là hai nút \(a\) và \(b\), ta có hai trường hợp như sau:
- Trường hợp 1: LCA của \(a\) và \(b\) khác \(a\) và \(b\):
- Trong trường hợp này, điều duy nhất ta có thể làm là nối xuống nút bé nhất nằm trong cây con gốc \(a\) hoặc nằm trong cây con gốc \(b\).
- Trường hợp 2: \(a\) là nút con của \(b\) hoặc ngược lại:
- Tại trường hợp này, mình sẽ mặc định \(a\) là nút con của \(b\).
- Với nút \(a\), ta sẽ nối xuống nút bé nhất nằm trong cây con gốc \(a\).
- Gọi \(b_1\) là nút nằm ngay bên dưới nút \(b\) trong đường đi từ \(a\) đến \(b\) (nút cha của \(b_1\) là \(b\)), vậy để nối dài thêm đường đi ta có thể nối với nút bé nhất chưa được tô màu nằm trong cây con gốc \(u\) với điều kiện là nút này không thuộc cây con gốc \(b_1\) (vì khi nối vào đường đi hiện tại, đường đi này sẽ bị rẽ nhánh).
Trong trường hợp 1 việc xử lí không quá khó, để lấy nút bé nhất chưa được tô màu nằm trong cây con gốc \(x\) ta sẽ quản lí một cây segment tree với nút \(x\) được lưu lại vị trí \(tin_x\) (thời điểm mà hàm dfs đi tới nút \(x\)). Rõ ràng việc tìm nút bé nhất trong cây con gốc \(x\) cũng là việc tìm giá trị bé nhất thuộc đoạn \([tin_x, tout_x]\) với \(s_x\) là số nút trong cây con gốc \(x\).
Trong trường hợp 2 việc xử lí sẽ rắc rối hơn khi \(a\) là nút con của \(b\). Trong trường hợp này, ta sẽ lấy giá trị bé nhất trong đoạn \([tin_u, tout_u] \setminus [tin_{b_1}, tout_{b_1}]\) và nó sẽ thành việc tìm giá trị bé nhất trên hai đoạn \([tin_u, tin_{b_1} - 1]\), \([tout_{b_1} + 1, tout_u]\).
Sau khi nối dài đường đi, ta sẽ chia bài toán trên cây con gốc \(u\) thành các bài toán con nhỏ hơn (các nút kề với các nút nằm trên đường đi mà ta đã tô màu, và chính bản thân nút \(u\) nếu như trong lúc tô màu ta chưa hề tô màu nút \(u\)). Khi đấy ta sẽ xử lí các bài toán con của các nút \(v\) (\(v\) kề với các nút đã được tô màu) rồi mới xử lí bài toán con bé hơn của nút \(u\), vì sau khi xử lí xong các bài toán con thấp hơn trước thì tại nút \(u\) ta sẽ chỉ có thể truy cập vào được những nút chưa bị đánh dấu.
Cuối cùng, ta cần đánh số lại màu của các nút sao cho đáp án thu được có giá trị bé nhất có thể.
Độ phức tạp: \(\mathcal{O}(n\cdot \log n)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 500005;
struct SegmentTree {
private:
int treeSize;
vector<int> nodes;
void initTree(int id, int low, int high) {
if (low == high) {
nodes[id] = 0;
return;
}
int mid = (low + high) / 2;
initTree(id * 2, low, mid);
initTree(id * 2 + 1, mid + 1, high);
nodes[id] = min(nodes[id * 2], nodes[id * 2 + 1]);
}
void update(int id, int low, int high, int pos, int val) {
if (low == high) {
nodes[id] = val;
return;
}
int mid = (low + high) / 2;
if (pos <= mid) {
update(id * 2, low, mid, pos, val);
} else {
update(id * 2 + 1, mid + 1, high, pos, val);
}
nodes[id] = min(nodes[id * 2], nodes[id * 2 + 1]);
}
int get(int id, int low, int high, int left, int right) {
if (low > right || high < left) {
return INT_MAX;
}
if (low >= left && high <= right) {
return nodes[id];
}
int mid = (low + high) / 2;
return min(get(id * 2, low, mid, left, right), get(id * 2 + 1, mid + 1, high, left, right));
}
public:
void init(int treeSize) {
this->treeSize = treeSize;
int tmp = 1;
while (tmp < treeSize) {
tmp *= 2;
}
nodes.resize(tmp * 2);
initTree(1, 1, treeSize);
}
void update(int pos, int val) {
update(1, 1, treeSize, pos, val);
}
int get(int left, int right) {
return get(1, 1, treeSize, left, right);
}
};
int numNode;
vector<int> adj[MAX_N];
int tin[MAX_N], tout[MAX_N], timer;
int parent[MAX_N][19], dep[MAX_N];
SegmentTree segmentTree;
int color[MAX_N];
void dfs(int node) {
tin[node] = ++timer;
for (auto u : adj[node]) {
if (u != parent[node][0]) {
parent[u][0] = node;
dep[u] = dep[node] + 1;
dfs(u);
}
}
tout[node] = timer;
}
bool is_parent(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int lca(int u, int v) {
if (is_parent(u, v)) {
return u;
}
if (is_parent(v, u)) {
return v;
}
for (int i = 18; i >= 0; i--) {
if (parent[u][i] != -1 && !is_parent(parent[u][i], v)) {
u = parent[u][i];
}
}
return parent[u][0];
}
int lift(int u, int h) {
for (int i = 18; i >= 0; i--) {
if (h & (1 << i)) {
u = parent[u][i];
}
}
return u;
}
int cnt;
int answer[MAX_N];
void add(int u) {
answer[u] = cnt;
segmentTree.update(tin[u], INT_MAX);
}
void solve(int x) {
cnt++;
int mnm1 = segmentTree.get(tin[x], tout[x]);
pair<int, int> cur = make_pair(mnm1, mnm1);
add(mnm1);
mnm1 = segmentTree.get(tin[x], tout[x]);
if (mnm1 <= numNode) {
int l = lca(cur.first, mnm1);
for (int u = mnm1; u != l; u = parent[u][0]) {
add(u);
}
if (cur.first != l) {
add(l);
for (int u = parent[cur.first][0]; u != l; u = parent[u][0]) {
add(u);
}
}
cur.second = mnm1;
} else {
return;
}
if (is_parent(cur.second, cur.first)) {
swap(cur.first, cur.second);
}
while (true) {
bool chk = false;
int mnm1 = segmentTree.get(tin[cur.second], tout[cur.second]);
if (mnm1 <= numNode) {
chk = true;
for (int u = mnm1; u != cur.second; u = parent[u][0]) {
add(u);
}
cur.second = mnm1;
}
if (is_parent(cur.first, cur.second)) {
int y = lift(cur.second, dep[cur.second] - dep[cur.first] - 1);
int l1 = tin[x], r1 = tin[y] - 1, l2 = tout[y] + 1, r2 = tout[x];
int mnm2 = min(segmentTree.get(l1, r1), segmentTree.get(l2, r2));
if (mnm2 <= numNode) {
chk = true;
int l = lca(mnm2, cur.first);
for (int u = mnm2; u != l; u = parent[u][0]) {
add(u);
}
if (l != cur.first) {
add(l);
for (int u = parent[cur.first][0]; u != l; u = parent[u][0]) {
add(u);
}
}
cur.first = mnm2;
}
} else {
int mnm2 = segmentTree.get(tin[cur.first], tout[cur.first]);
if (mnm2 <= numNode) {
chk = true;
for (int u = mnm2; u != cur.first; u = parent[u][0]) {
add(u);
}
cur.first = mnm2;
}
}
if (!chk) {
break;
}
}
int l = lca(cur.first, cur.second);
for (int u = cur.first;; u = parent[u][0]) {
for (auto v : adj[u]) {
if (v == parent[u][0] || answer[v]) {
continue;
}
solve(v);
}
if (u == l) {
break;
}
}
for (int u = cur.second; u != l; u = parent[u][0]) {
for (auto v : adj[u]) {
if (v != parent[u][0] && !answer[v]) {
solve(v);
}
}
}
if (l != x) {
solve(x);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> numNode;
for (int i = 1; i <= numNode - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(parent, -1, sizeof(parent));
dfs(1);
for (int i = 1; i <= 18; i++) {
for (int u = 1; u <= numNode; u++) {
if (parent[u][i - 1] != -1) {
parent[u][i] = parent[parent[u][i - 1]][i - 1];
}
}
}
segmentTree.init(numNode);
for (int u = 1; u <= numNode; u++) {
segmentTree.update(tin[u], u);
}
cnt = 0;
solve(1);
cnt = 0;
for (int u = 1; u <= numNode; u++) {
if (!color[answer[u]]) {
color[answer[u]] = ++cnt;
}
cout << color[answer[u]] << ' ';
}
return 0;
}
Bình luận