#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME (1.0 * clock() / CLOCKS_PER_SEC)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 1e5 + 5;
const int oo = 1e9, mod = 1e9 + 7;
int n, m, k, visited[N], root=0, special_node=0, dp[N][2][2][2][2], dad[N], head[N];
string s;
vector<int> edges[N];
/*
Subtask 1: Nếu n$4==0 N/2 thằng xanh vì là màu tròn
Subtask 2: Bitmask set các màu O(2^20)
Nhận xét: Ở đây, bản chất chính là một cây +1 cạnh tạo thành 1 vòng tròn
Nếu vòng tròn là lẻ => Vòng tròn đó sẽ...
Nếu vòng tròn là chẵn =>
Còn các trường hợp còn lại, ta tô màu theo các tầng khác nhau (Depth)
Ta nhận thấy đồ thị chỉ gồm có 1 chu trình, trong đó mỗi node trong chu trình có thể có gốc ở đó
Dùng dfs => xác định chu trình => Xoá cạnh
2 đỉnh của cạnh sẽ có 1 đỉnh là gốc, mọt đỉnh còn lại là đỉnh đặc biệt. Sau khi xoá cạnh, tạo thành một cây
có gốc con như ta đã tìm được.
Giải bằng phương pháp quy hoạch động
Ta cố định các cách chọn tô màu cho cạnh root và special node (4 khả năng), thêm thông tin vào trong hàm dp.
Trạng thái biểu thị cho node đang xét và mô tả cây con của node đó trên 5 thông số: dp[x][me][up][rt][sp]
Cho thấy số lượng node đen cần là nhỏ nhất trong cây con của x,
nếu màu của node x được viết trong trạng thái me, màu của cha x là up, màu của root là rt,
màu của special node là sp.
Trong trạng thái ra cho rặng cha của x đã có sẵn đỉnh lân cận màu đen, do đó ta chỉ cần làm rõ màu của các
đỉnh trong cây con gốc x.
Quá trình chuyển đổi như sau. Trước tiên, chúng ta xác định các trường hợp cờ ở trạng thái không khớp với nhau
(vì vậy câu trả lời ngay lập tức là -1 cho trạng thái này). Điều này xảy ra khi:
- x là gốc, me != rt;
- x là cạnh đặc biệt, me != sp
- x là cạnh đặc biệt, rt i up là đen, => x có 2 hàng xóm
Giờ ta sẽ làm rõ nếu node đang xét x đã có hàng xóm màu đen. Nó đúng trong trường hợp up là đen, hoặc x là gốc
và sp là đen, haowcj x là sp và rt là đen. Nếu x đã được phủ, không có cạnh con nào được phép màu đen, do vậy
kết quả được biểu diễn bằng dp[v][white][me][rt][sp] tất cả các node con của x, còn nếu x chưa được phủ, ta chọn
1 trong các con của chúng là đen, còn lại là trắng. Ta tính tổng như trên, ngoại trừ việc đổi 1 trong các con
thành black. Thử cho mỗi con và cho kết quả bé nhất
*/
int nadi (int x) {
if (x == head[x]) return x;
return head[x] = nadi(head[x]);
}
void findCyc(int u) {
visited[u]=true;
for (auto v: edges[u]) {
if (visited[v]==1) {
root=u;
special_node=v;
} else {
findCyc(v);
}
}
}
void findPar(int u, int par) {
dad[u]=par;
for (auto v: edges[u]) {
if (v==par) continue;
findPar(v, u);
}
}
int dpontree(int x, int me, int up, int rt, int sp) {
if (dp[x][me][up][rt][sp]!=-1) return dp[x][me][up][rt][sp];
int res=oo;
bool chk=1;
if (x==root && me!=rt) chk=0;
if (x==special_node && me!=sp) chk=0;
if (x==special_node && up && rt) chk=0;
if (!chk) return dp[x][me][up][rt][sp]=oo;
bool covered=0;
if (up) covered=1;
if (x==root && sp) covered=1;
if (x==special_node && rt) covered=1;
int sum=me;
for (auto v: edges[x]) {
if (v==dad[x]) continue;
sum+=dpontree(v, 0, me, rt, sp);
}
if (covered) {
res=min(res, sum);
} else {
for (auto v: edges[x]) {
if (v==dad[x]) continue;
int val=sum-dpontree(v, 0, me, rt, sp) + dpontree(v, 1, me, rt, sp);
res=min(res, val);
}
}
return dp[x][me][up][rt][sp]=res;
}
void process() {
memset(dp, -1, sizeof(dp));
cin >> n;
foru(i,1,n) head[i]=i;
foru(i,1,n) {
int a, b;
cin >> a >> b;
int pa = nadi(a);
int pb = nadi(b);
if (pa == pb) {
root = a;
special_node = b;
} else {
head[pa] = pb;
edges[a].push_back(b);
edges[b].push_back(a);
}
}
findPar(root, 0);
int sol = oo;
foru(rt, 0 ,1) {
foru(sp, 0 ,1) {
sol = min(sol, dpontree(root, rt, 0, rt, sp));
}
}
/*for (int i=1; i<=n; i++) {
cout << dad[i] << ' ';
}
cout << '\n';*/
if (sol == oo || sol<=0) cout << -1; else cout << sol;
return;
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
//freopen(".inp", "r", stdin);
//freopen(".out", "w", stdout);
process();
cerr << "Time elapsed: " << __TIME << " s.\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9816 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 3 |
Correct |
2 ms |
9712 KB |
Output is correct |
| 4 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 5 |
Correct |
115 ms |
26964 KB |
Output is correct |
| 6 |
Correct |
132 ms |
27376 KB |
Output is correct |
| 7 |
Correct |
117 ms |
26852 KB |
Output is correct |
| 8 |
Correct |
138 ms |
26916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9816 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 3 |
Correct |
2 ms |
9712 KB |
Output is correct |
| 4 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 5 |
Correct |
115 ms |
26964 KB |
Output is correct |
| 6 |
Correct |
132 ms |
27376 KB |
Output is correct |
| 7 |
Correct |
117 ms |
26852 KB |
Output is correct |
| 8 |
Correct |
138 ms |
26916 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
9816 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
