Submission #862247

#	Time	Username	Problem	Language	Result	Execution time	Memory
862247		TAhmed33	Logičari (COCI21_logicari)	C++98	110 / 110	167 ms	29468 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e10;
const int MAXN = 1e5 + 25;
vector <int> adj[MAXN];
pair <int, int> bad;
bool vis[MAXN];
void dfs (int pos, int par = -1) {
	vis[pos] = 1;
	for (auto j : adj[pos]) {
		if (j == par) continue;
		if (vis[j]) {
			bad = {j, pos};
		} else {
			dfs(j, pos);
		}
	}
}
int dp[MAXN][2][2][2][2];
void dfs2 (int pos, int par) {
	for (int j = 0; j < (int)adj[pos].size(); j++) {
		if (adj[pos][j] == par) {
			adj[pos].erase(adj[pos].begin() + j);
		}
	}
	for (auto j : adj[pos]) dfs2(j, pos);
}
int ans (int pos, int w, int x, int y, int z) {
	if (pos == bad.second && w != z) return inf;
	if (pos == bad.first && w != y) return inf;
	int &ret = dp[pos][w][x][y][z];
	if (ret != -1) return ret;
	int flag = x;
	flag += (pos == bad.first && z);
	flag += (pos == bad.second && y);
	for (auto j : adj[pos]) flag += (j == bad.second && z);
	if (flag > 1) return ret = inf;
	if (flag) {
		int sum = 0;
		for (auto j : adj[pos]) {
			if (j == bad.second) {
				sum += ans(j, z, w, y, z);
			} else {
				sum += ans(j, 0, w, y, z);
			}
		}
		return ret = w + sum;
	}
	int sum = 0;
	for (auto j : adj[pos]) {
		sum += ans(j, 0, w, y, z);
	}
	int mn = inf;
	for (auto j : adj[pos]) {
		mn = min(mn, ans(j, 1, w, y, z) - ans(j, 0, w, y, z));
	}
	return ret = w + sum + mn;
}
signed main () {
	memset(dp, -1, sizeof(dp));
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1);
	for (int i = 0; i < (int)adj[bad.first].size(); i++) {
		if (adj[bad.first][i] == bad.second) {
			adj[bad.first].erase(adj[bad.first].begin() + i);
			break;
		}
	}
	for (int i = 0; i < (int)adj[bad.second].size(); i++) {
		if (adj[bad.second][i] == bad.first) {
			adj[bad.second].erase(adj[bad.second].begin() + i);
			break;
		}
	}
	dfs2(bad.first, -1);
	int x = min({
		ans(bad.first, 0, 0, 0, 1),
		ans(bad.first, 0, 0, 0, 0),
		ans(bad.first, 1, 0, 1, 0),
		ans(bad.first, 1, 0, 1, 1)
	});
	cout << (x >= inf ? -1 : x) << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 40 / 40
• Subtask 4: 50 / 50