Submission #862164

# Submission time Handle Problem Language Result Execution time Memory
862164 2023-10-17T15:05:22 Z Mizo_Compiler Logičari (COCI21_logicari) C++14
Compilation error
0 ms 0 KB
#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, 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);
	}
	ins[u] = false;
}

int get(int u, int x, int val, int p = -1) {
	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] || v == p)continue;
			fx = true;
			int f = get(v, val, 0, u), s = sol2(v, val, 1, u);
			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] || v == p)continue;
			ret += get(v, val, 0, u);
			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++) {
				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";
}


Compilation message

Main.cpp: In function 'int get(int, int, int, int)':
Main.cpp:49:35: error: 'sol2' was not declared in this scope
   49 |    int f = get(v, val, 0, u), s = sol2(v, val, 1, u);
      |                                   ^~~~