oj.uz

Submission #872889

# Submission time Handle Problem Language Result Execution time Memory
872889 2023-11-14T03:49:16 Z tsumondai Logičari (COCI21_logicari) C++14
60 / 110
 197 ms 32672 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 == 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 16984 KB Output is correct
2 Correct 3 ms 17144 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 197 ms 32672 KB Output is correct
6 Correct 140 ms 32592 KB Output is correct
7 Correct 133 ms 32500 KB Output is correct
8 Correct 129 ms 32592 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 17144 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 197 ms 32672 KB Output is correct
6 Correct 140 ms 32592 KB Output is correct
7 Correct 133 ms 32500 KB Output is correct
8 Correct 129 ms 32592 KB Output is correct
9 Correct 2 ms 16988 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 2 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 2 ms 16984 KB Output is correct
15 Correct 3 ms 16988 KB Output is correct
16 Correct 2 ms 16988 KB Output is correct
17 Correct 3 ms 16988 KB Output is correct
18 Correct 3 ms 17048 KB Output is correct
19 Correct 3 ms 16988 KB Output is correct
20 Correct 3 ms 16988 KB Output is correct
21 Correct 4 ms 16984 KB Output is correct
22 Correct 3 ms 17048 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 17052 KB Output is correct
27 Correct 3 ms 16988 KB Output is correct
28 Correct 3 ms 17060 KB Output is correct
29 Correct 4 ms 16988 KB Output is correct
30 Correct 3 ms 17052 KB Output is correct
31 Correct 3 ms 16984 KB Output is correct
32 Correct 3 ms 16988 KB Output is correct
33 Correct 136 ms 21080 KB Output is correct
34 Correct 73 ms 21072 KB Output is correct
35 Correct 80 ms 21084 KB Output is correct
36 Correct 72 ms 21292 KB Output is correct
37 Correct 20 ms 18268 KB Output is correct
38 Incorrect 75 ms 21172 KB Output isn't correct
39 Halted 0 ms 0 KB -