Submission #862176

#	Time	Username	Problem	Language	Result	Execution time	Memory
862176		Mizo_Compiler	Logičari (COCI21_logicari)	C++14	110 / 110	91 ms	30160 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
const int N = 1e5+5;
int n, dp[N][2][2], dp2[N][2][2][2][2], tr[N], dp3[N][2][2];
vector<int> adj[N], cyc;
bool inc[N], ins[N], vis[N];
 
void get_cyc(int u, int p) {
	if (!cyc.empty())return;
	if (ins[u]) {
		cyc.pb(u);
		int cur = tr[u];
		inc[u] = true;
		while (cur != u) {
			cyc.pb(cur);
			inc[cur] = true;
			cur = tr[cur];
		}
		return;
	}
	if (vis[u])return;
	vis[u] = ins[u] = true;
	for (auto &v : adj[u]) {
		if (v == p)continue;
		tr[u] = v;
		get_cyc(v, u);
		if (!cyc.empty())return;
	}
	ins[u] = false;
}
 
int sol2(int u, int p, int val, int pv) {
	int &ret = dp[u][val][pv];
	if (~ret)return ret;
	ret = val;
	if (!pv) {
		int mn = -1e6;
		int f, s;
		bool fl = false, f2 = false, fx = false;
		for (auto &v : adj[u]) {
			if (v == p || inc[v])continue;
			fx = true;
			f = sol2(v, u, 0, val), s = sol2(v, u, 1, val);
			if (f == s && f == int(1e6))return ret = int(1e6);
			if (f == int(1e6)) {
				if (fl)return ret = int(1e6);
				ret += (mn == -1e6 ? 0 : mn);
				mn = 1e6;
				fl = true;
				ret += s;
				continue;
			}
			if (s == int(1e6)) {
				ret += f;
				continue;
			}
			if (f-s > mn) {
				ret += (mn == -1e6 ? 0 : mn);
				mn = f-s;
				ret += s;
				f2 = true;
			} else {
				ret += f;
			}
		}
		if (!fx || (!fl && !f2))return ret = int(1e6);
	} else {
		for (auto &v : adj[u]) {
			if (v == p || inc[v])continue;
			ret += sol2(v, u, 0, val);
			if (ret > int(1e6))return ret = int(1e6);
		}
	}
	ret = min(ret, int(1e6));
	return ret;
}
 
int get(int u, int x, int val) {
	int &ret = dp3[u][x][val];
	if (~ret)return ret;
	ret = 0;
	bool fx = false;
	if (!x) {
		int mn = -1e6;
		bool fl = false, f2 = false;
		for (auto &v : adj[u]) {
			if (inc[v])continue;
			fx = true;
			int f = sol2(v, u, 0, val), s = sol2(v, u, 1, val);
			if (f == s && f == int(1e6))return ret = int(1e6);
			if (f == int(1e6)) {
				if (fl)return ret = int(1e6);
				ret += (mn == -1e6 ? 0 : mn);
				mn = 1e6;
				fl = true;
				ret += s;
				continue;
			}
			if (s == int(1e6)) {
				ret += f;
				continue;
			}
			if (f-s > mn) {
				ret += (mn == -1e6 ? 0 : mn);
				mn = f-s;
				ret += s;
				f2 = true;
			} else {
				ret += f;
			}
		}
		if (!fx)return ret = int(1e6);
		if (!fl && !f2)return ret = int(1e6);
	} else {
		for (auto &v : adj[u]) {
			if (inc[v])continue;
			ret += sol2(v, u, 0, val);
			if (ret > int(1e6))return ret = int(1e6);
		}
	}
	return ret;
}
 
int sol(int i, int ls, int nls, int f, int nf) {
	int &ret = dp2[i][ls][nls][f][nf];
	if (~ret)return ret;
	if (!i) {
		int c1 = get(cyc[i], 0, 0) + sol(i+1, 0, 1, 0, 1);
		c1 = min({c1, int(1e6), get(cyc[i], 1, 0) + sol(i+1, 0, 0, 0, 0)});
		int c2 = get(cyc[i], 0, 1) + 1 + sol(i+1, 1, 1, 1, 1);
		c2 = min({c2, int(1e6), get(cyc[i], 1, 1) + 1 + sol(i+1, 1, 0, 1, 0)});
		return ret = min({int(1e6), c1, c2});
	} else if (i == sz(cyc) - 1) {
		if (f && ls)return ret = int(1e6);
		if (nf+nls == 1)return ret = int(1e6);
		if (nf + nls == 0) {
			if (f + ls == 0) {
				return ret = min(int(1e6), get(cyc[i], 0, 1) + 1);
			} else {
				return ret = min(int(1e6), 1 + get(cyc[i], 1, 1));
			}
		}
		if (f + ls == 0)return ret = get(cyc[i], 0, 0);
		return ret = get(cyc[i], 1, 0);
	} else if (i == 1) {
		if (ls) {
			if (nf)return ret = min(int(1e6), get(cyc[i], 1, 0) + sol(i+1, 0, 1, f, nf));
			int c1 = get(cyc[i], 1, 1) + 1 + sol(i+1, 1, 1, f, 1);
			int c2 = get(cyc[i], 1, 0) + sol(i+1, 0, 1, f, 0);
			return ret = min({int(1e6), c1, c2});
		}
		if (nf)return ret = min(int(1e6), get(cyc[i], 0, 0) + sol(i+1, 0, 1, f, nf));
		int c1 = get(cyc[i], 0, 1) + 1 + sol(i+1, 1, 1, f, 1);
		c1 = min(c1, get(cyc[i], 1, 1) + 1 + sol(i+1, 1, 0, f, 1));
		int c2 = get(cyc[i], 0, 0) + sol(i+1, 0, 1, f, 0);
		c2 = min(c2, get(cyc[i], 1, 0) + sol(i+1, 0, 0, f, 0));
		return ret = min({int(1e6), c1, c2});
	} else {
		if (!nls) {
			int c1 = get(cyc[i], ls, 1)+1+sol(i+1, 1, 1, f, nf);
			c1 = min(c1, get(cyc[i], 1, 1)+1+sol(i+1, 1, ls, f, nf));
			return ret = min(int(1e6), c1);
		}
		int c1 = get(cyc[i], ls, 0)+sol(i+1, 0, 1, f, nf);
		c1 = min(c1, get(cyc[i], 1, 0)+sol(i+1, 0, ls, f, nf));
		return ret = min(int(1e6), c1);
	}
	return ret;
}
 
int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				dp[i][j][k] = dp3[i][j][k] = -1;
				for (int l = 0; l < 2; l++) {
					for (int m = 0; m < 2; m++) {
						dp2[i][j][k][l][m] = -1;
					}
				}
			}
		}
	}
	get_cyc(0, 0);
	int x = sol(0, 0, 0, 0, 0);
	cout << (x > n ? -1 : x) << "\n";
}

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