oj.uz

Submission #872882

# Submission time Handle Problem Language Result Execution time Memory
872882 2023-11-14T03:28:36 Z tsumondai Logičari (COCI21_logicari) C++14
10 / 110
 132 ms 32676 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#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 = 1e18, 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) 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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 2 ms 16984 KB Output is correct
4 Correct 3 ms 16984 KB Output is correct
5 Correct 128 ms 32592 KB Output is correct
6 Correct 124 ms 32676 KB Output is correct
7 Correct 128 ms 32592 KB Output is correct
8 Correct 132 ms 32452 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2 ms 17048 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16984 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Incorrect 3 ms 16988 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2 ms 17048 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16984 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Incorrect 3 ms 16988 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 2 ms 16984 KB Output is correct
4 Correct 3 ms 16984 KB Output is correct
5 Correct 128 ms 32592 KB Output is correct
6 Correct 124 ms 32676 KB Output is correct
7 Correct 128 ms 32592 KB Output is correct
8 Correct 132 ms 32452 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 2 ms 17048 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 3 ms 16984 KB Output is correct
14 Correct 3 ms 16988 KB Output is correct
15 Correct 3 ms 16988 KB Output is correct
16 Correct 3 ms 16988 KB Output is correct
17 Incorrect 3 ms 16988 KB Output isn't correct
18 Halted 0 ms 0 KB -