oj.uz

Submission #862246

# Submission time Handle Problem Language Result Execution time Memory
862246 2023-10-17T20:21:56 Z TAhmed33 Logičari (COCI21_logicari) C++
10 / 110
 1000 ms 27828 KB 
#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 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 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 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 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15196 KB Output is correct
2 Correct 2 ms 15196 KB Output is correct
3 Correct 2 ms 15196 KB Output is correct
4 Correct 3 ms 15192 KB Output is correct
5 Execution timed out 1056 ms 27828 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15196 KB Output is correct
2 Correct 2 ms 15196 KB Output is correct
3 Correct 2 ms 15192 KB Output is correct
4 Correct 2 ms 15192 KB Output is correct
5 Correct 2 ms 15196 KB Output is correct
6 Correct 2 ms 15388 KB Output is correct
7 Correct 2 ms 15196 KB Output is correct
8 Correct 2 ms 15196 KB Output is correct
9 Correct 2 ms 15196 KB Output is correct
10 Correct 2 ms 15196 KB Output is correct
11 Correct 18 ms 15196 KB Output is correct
12 Correct 3 ms 15196 KB Output is correct
13 Execution timed out 1020 ms 15448 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15196 KB Output is correct
2 Correct 2 ms 15196 KB Output is correct
3 Correct 2 ms 15196 KB Output is correct
4 Correct 3 ms 15192 KB Output is correct
5 Execution timed out 1056 ms 27828 KB Time limit exceeded
6 Halted 0 ms 0 KB -