oj.uz

Submission #872890

# Submission time Handle Problem Language Result Execution time Memory
872890 2023-11-14T03:52:11 Z tsumondai Logičari (COCI21_logicari) C++14
110 / 110
 133 ms 33620 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 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 >= mod) 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 16984 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 126 ms 32436 KB Output is correct
6 Correct 127 ms 32592 KB Output is correct
7 Correct 133 ms 32444 KB Output is correct
8 Correct 124 ms 32680 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 2 ms 16988 KB Output is correct
9 Correct 2 ms 16988 KB Output is correct
10 Correct 2 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 2 ms 16988 KB Output is correct
9 Correct 2 ms 16988 KB Output is correct
10 Correct 2 ms 16988 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 16988 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 Correct 3 ms 16988 KB Output is correct
18 Correct 3 ms 16988 KB Output is correct
19 Correct 3 ms 16988 KB Output is correct
20 Correct 3 ms 16984 KB Output is correct
21 Correct 3 ms 16988 KB Output is correct
22 Correct 3 ms 16984 KB Output is correct
23 Correct 3 ms 16988 KB Output is correct
24 Correct 3 ms 16988 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 126 ms 32436 KB Output is correct
6 Correct 127 ms 32592 KB Output is correct
7 Correct 133 ms 32444 KB Output is correct
8 Correct 124 ms 32680 KB Output is correct
9 Correct 3 ms 16984 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 2 ms 16988 KB Output is correct
13 Correct 3 ms 16988 KB Output is correct
14 Correct 4 ms 16988 KB Output is correct
15 Correct 2 ms 16988 KB Output is correct
16 Correct 2 ms 16988 KB Output is correct
17 Correct 2 ms 16988 KB Output is correct
18 Correct 2 ms 16988 KB Output is correct
19 Correct 3 ms 16988 KB Output is correct
20 Correct 3 ms 16988 KB Output is correct
21 Correct 3 ms 16988 KB Output is correct
22 Correct 3 ms 16988 KB Output is correct
23 Correct 3 ms 16988 KB Output is correct
24 Correct 3 ms 16988 KB Output is correct
25 Correct 3 ms 16988 KB Output is correct
26 Correct 3 ms 16988 KB Output is correct
27 Correct 3 ms 16988 KB Output is correct
28 Correct 3 ms 16984 KB Output is correct
29 Correct 3 ms 16988 KB Output is correct
30 Correct 3 ms 16984 KB Output is correct
31 Correct 3 ms 16988 KB Output is correct
32 Correct 3 ms 16988 KB Output is correct
33 Correct 74 ms 20060 KB Output is correct
34 Correct 101 ms 20248 KB Output is correct
35 Correct 71 ms 20060 KB Output is correct
36 Correct 75 ms 20256 KB Output is correct
37 Correct 18 ms 17752 KB Output is correct
38 Correct 77 ms 20372 KB Output is correct
39 Correct 8 ms 17244 KB Output is correct
40 Correct 79 ms 21308 KB Output is correct
41 Correct 57 ms 22224 KB Output is correct
42 Correct 65 ms 22088 KB Output is correct
43 Correct 105 ms 33620 KB Output is correct
44 Correct 88 ms 27748 KB Output is correct