#include <iostream>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <map>
#include <deque>
#include <stdio.h>
using namespace std;
struct DisjointSetUnion {
vector<int> parent;
vector<int> sz;
void join (int u, int v) {
u = find_head(u), v = find_head(v);
if (u == v) {
return;
}
if (sz[u] > sz[v]) {
swap(u, v);
}
parent[u] = v;
sz[v] += sz[u];
}
int find_head (int x) {
return ((x == parent[x]) ? x : find_head(parent[x]));
}
DisjointSetUnion (int n) {
for (int i = 0; i < n; i++) {
parent.push_back(i), sz.push_back(1);
}
}
};
const int MX = 1000;
struct Tree {
vector<vector<int>> adj;
int64_t dp[MX][2][2][2];
//dp[node][colors of parent][color of me][sum of colors of children]
map<int,int> color;
map<int,int> color_count;
void dfs (int curNode, int prevNode) {
//cout << color_count[1] << '\n';
for (int i: adj[curNode]) {
if (i != prevNode) {
dfs (i, curNode);
}
}
//cout << adj[2].size() << '\n';
for (int cp = 0; cp <= 1; cp++) { //is the parent (prevNode) blue eyed or not?
for (int cm = 0; cm <= 1; cm++) { //is curNode blue eyed or not?
for (int cc = 0; cc <= 1; cc++) { //how many children of curNode are blue-eyed (at most 1)
if (cc == 1 and cp == 1) {
continue;
}
if (curNode == 0 and cp != 0) {
continue;
}
if (color_count.count(curNode) and cc + cp != color_count[curNode]) {
continue;
}
if (!color_count.count(curNode) and cc + cp != 1) {
continue;
}
if (color.count(curNode) and cm != color[curNode]) {
continue;
}
if (adj[curNode].size() == 1 and curNode != 0) {
//if (cp != 1 and cc != 0) continue;
if (cp == 1 and cm == 0 and cc == 0) {
dp[curNode][1][0][0] = 0;
}
if (cp == 1 and cm == 1 and cc == 0) {
dp[curNode][1][1][0] = 1;
}
//return;
continue;
}
if (cc == 1) {
int64_t sum = (cm == 1);
for (int i: adj[curNode]) {
if (i != prevNode) {
sum += min(dp[i][cm][cc][0], dp[i][cm][cc][1]);
}
}
for (int i: adj[curNode]) {
if (i != prevNode) {
dp[curNode][cp][cm][cc] = min(dp[curNode][cp][cm][cc], sum - min(dp[i][cm][cc][0], dp[i][cm][cc][1]) + min(dp[i][cm][1][0], dp[i][cm][1][1]));
}
}
} else {
assert(cc == 0);
dp[curNode][cp][cm][cc] = (cm == 1);
for (int i: adj[curNode]) {
if (i != prevNode) {
dp[curNode][cp][cm][cc] += min(dp[i][cm][0][0], dp[i][cm][0][1]);
}
}
}
}
}
}
}
void clear () {
for (int i = 0; i < MX; i++) {
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= 1; k++) {
dp[i][j][k][0] = 1e8;
dp[i][j][k][1] = 1e8;
}
}
}
}
int solve () {
clear();
dfs(0, 0);
int64_t mn = 1e8;
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= 1; k++) {
mn = min(mn, dp[0][0][j][k]);
}
}
/*
for (int curNode = 0; curNode < (int)adj.size(); curNode++) {
for (int i = 0; i <= 1; i++) {
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= 1; k++) {
cout << curNode << " " << i << " " << j << " " << k << " " << dp[curNode][i][j][k] << '\n';
}
}
}
}
*/
color.clear();
color_count.clear();
return mn;
}
void add_edge (int u, int v) {
adj[u].push_back(v), adj[v].push_back(u);
}
Tree (int n) {
adj.resize(n);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
DisjointSetUnion dsu(n);
Tree myTree(n);
pair<int,int> special_edge;
for (int i = 0; i < n; i++) {
int u, v;
cin >> u >> v;
--u, --v;
if (dsu.find_head(u) == dsu.find_head(v)) {
special_edge = make_pair(u, v);
continue;
}
myTree.add_edge(u, v);
dsu.join(u, v);
}
//cout << special_edge.first << " " << special_edge.second << '\n';
int mn = 1e8;
for (int dx = 0; dx <= 1; dx++) {
for (int dy = 0; dy <= 1; dy++) {
myTree.color[special_edge.first] = dx;
myTree.color_count[special_edge.first] = 1 - dy;
myTree.color[special_edge.second] = dy;
myTree.color_count[special_edge.second] = 1 - dx;
//cout << myTree.color_count[1] << '\n';
int res = myTree.solve();
//cout << res << '\n';
mn = min(res, mn);
//cout << "------------------\n";
}
}
cout << ((mn == (int)1e8) ? -1 : mn);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
