oj.uz

Submission #626750

# Submission time Handle Problem Language Result Execution time Memory
626750 2022-08-11T18:09:20 Z vovamr Logičari (COCI21_logicari) C++17
10 / 110
 160 ms 19852 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 1e5 + 10;
ve<int> gr[N];
int v1, v2;
ll dp[N][2][2];

int used[N];
inline void dfs1(int v, int p) {
	used[v] = 1;
	for (auto &to : gr[v]) {
		if (to == p) continue;

		if (used[to]) v1 = v, v2 = to;
		else dfs1(to, v);
	}
}

inline void dfs(int v, int p, const int &t1, const int &t2) {
	for (auto &to : gr[v]) {
		if (to == p) continue;
		if ((v == v1 && to == v2) || (v == v2 && to == v1)) continue;
		dfs(to, v, t1, t2);
	}

	ll sum = 0;

	// 0, 0
	dp[v][0][0] = 0;
	for (auto &to : gr[v]) {
		if (to == p) continue;
		if ((v == v1 && to == v2) || (v == v2 && to == v1)) continue;
		dp[v][0][0] += dp[to][0][1];
	}
	chmin(dp[v][0][0], iinf * 1ll);

	// 1, 0
	sum = 0;
	for (auto &to : gr[v]) {
		if (to == p) continue;
		if ((v == v1 && to == v2) || (v == v2 && to == v1)) continue;
		sum += dp[to][0][0];
	} dp[v][1][0] = min(iinf * 1ll, sum + 1);

	// 0, 1
	sum = 0;
	dp[v][0][1] = iinf;
	for (auto &to : gr[v]) {
		if (to == p) continue;
		if ((v == v1 && to == v2) || (v == v2 && to == v1)) continue;
		sum += dp[to][0][1];
	}
	for (auto &to : gr[v]) {
		if (to == p) continue;
		if ((v == v1 && to == v2) || (v == v2 && to == v1)) continue;
		chmin(dp[v][0][1], sum - dp[to][0][1] + dp[to][1][1]);
	}

	// 1, 1
	sum = 0;
	dp[v][1][1] = iinf;
	for (auto &to : gr[v]) {
		if (to == p) continue;
		if ((v == v1 && to == v2) || (v == v2 && to == v1)) continue;
		sum += dp[to][0][0];
	}
	for (auto &to : gr[v]) {
		if (to == p) continue;
		if ((v == v1 && to == v2) || (v == v2 && to == v1)) continue;
		chmin(dp[v][1][1], 1 + sum - dp[to][0][0] + dp[to][1][0]);
	}

	if (v == v1) {
		dp[v][!t1][0] = dp[v][!t1][1] = iinf;
		if (t2) dp[v][t1][0] = iinf;
	}
	else if (v == v2) {
		dp[v][!t2][0] = dp[v][!t2][1] = iinf;
		if (t1) dp[v][t2][0] = iinf;
	}
}

inline void solve() {
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int v, u;
		cin >> v >> u, --v, --u;
		gr[v].pb(u), gr[u].pb(v);
	}
	dfs1(0, 0);

	ll ans = iinf;
	for (int t1 : {0, 1}) {
		for (int t2 : {0, 1}) {

			for (int i = 0; i < n; ++i) {
				for (int j : {0, 1}) {
					for (int k : {0, 1}) {
						dp[i][j][k] = iinf;
					}
				}
			}

			dfs(v1, v1, t1, t2);
			chmin(ans, dp[v1][t1][!t2]);
//			if (dp[v1][t1][!t2] != iinf) {
//				cout << v1 + 1 << " " << v2 + 1 << " " << t1 << " " << t2 << " " << dp[v1][t1][!t2] << '\n';
//			}
		}
	}

	cout << (ans > n ? -1 : ans);
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2672 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 133 ms 19848 KB Output is correct
6 Correct 160 ms 19852 KB Output is correct
7 Correct 120 ms 19732 KB Output is correct
8 Correct 121 ms 19744 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 3 ms 2676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 3 ms 2676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2672 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 133 ms 19848 KB Output is correct
6 Correct 160 ms 19852 KB Output is correct
7 Correct 120 ms 19732 KB Output is correct
8 Correct 121 ms 19744 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Incorrect 3 ms 2676 KB Output isn't correct
11 Halted 0 ms 0 KB -