Submission #872889

#	Time	Username	Problem	Language	Result	Execution time	Memory
872889		tsumondai	Logičari (COCI21_logicari)	C++14	60 / 110	197 ms	32672 KiB

Main

#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 min(int a, int b) {
	if (a>b) return b; else return a;
}

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 ok = 1;
    if (x == root && me != rt) ok = 0;
    if (x == special_node && me != sp) ok = 0;
    if (x == special_node && up && rt) ok = 0;
    if (!ok) 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 sus : edges[x]) {
        if (sus == dad[x]) continue;
        sum += dpontree(sus, 0, me, rt, sp);
    }

    if (covered) {
        res = min(res, sum);
    } else {
        for (auto sus : edges[x]) {
            if (sus == dad[x]) continue;
            int val = sum - dpontree(sus, 0, me, rt, sp) + dpontree(sus, 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) {
        	int cal=dpontree(root, rt, 0, rt, sp);
        	if (cal <= 0) continue;
            sol = min(sol, cal);
        }
    }

    /*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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 40 / 40
• Subtask 4: 0 / 50