Submission #1272294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272294		altern23	Logičari (COCI21_logicari)	C++20	0 / 110	2 ms	572 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 1e5;
const ll INF = 1e18;
const int MOD = 1e9 + 7;

vector<ll> v, adj[MAXN + 5];

ll dp[MAXN + 5][4], dp2[MAXN + 5][4][4];
ll vis[MAXN + 5], is_cycle[MAXN + 5], p[MAXN + 5];

ll st, en;

void dfs(ll idx, ll par){
	vis[idx] = 1;
	for(auto i : adj[idx]){
		if(i == par) continue;
		if(vis[i] == 1){
			ll st = idx, en = i;
			for(;st != en;){
				v.push_back(st);
				is_cycle[st] = 1;
				st = p[st];
			}
			v.push_back(en);
			is_cycle[en] = 1;
		}
		else if(!vis[i]){
			p[i] = idx;
			dfs(i, idx);
		}
	}
	vis[idx] = 2;
}

void dfs2(ll idx, ll par){
	bool is_leaf = 1;
	for(auto i : adj[idx]){
		if(i != par && !is_cycle[i]){
			dfs2(i, idx);
			is_leaf = 0;
			for(int j = 0; j < 4; j++){
				dp[idx][(j + 1) % 4] = min(dp[idx][(j + 1) % 4], dp[i][j] + ((j + 1) % 4 <= 1));
			}
		}
	}
	
	if(is_leaf){
		dp[idx][3] = 0, dp[idx][0] = 1;
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N; cin >> N;
		for(int i = 1; i <= N; i++){
			ll u, v; cin >> u >> v;
			adj[u].push_back(v), adj[v].push_back(u);
		}
		
		dfs(1, -1);
		
		for(int i = 1; i <= N; i++){
			for(int j = 0; j < 4; j++){
				dp[i][j] = 4LL * INF;
			}
		}
		
		for(int i = 1; i <= N; i++){
			if(is_cycle[i]){
				dfs2(i, -1);
			}
		}
		
		ll M = (int)v.size() - 1;
		for(int i = 0; i <= M; i++){
			for(int j = 0; j < 4; j++){
				for(int k = 0; k < 4; k++) dp2[i][j][k] = INF;
			}
		}
		
		for(int i = 0; i < 4; i++) dp2[0][i][i] = dp[v[0]][i];

		for(int i = 1; i <= M; i++){
			for(int j = 0; j < 4; j++){
				// 0 -> biru belum ada pasangan
				// 1 -> biru sudah ada pasangan
				// 2 -> putih sudah ada pasangan
				// 3 -> putih belum ada pasangan
				dp2[i][j][0] = min({dp2[i][j][0], dp2[i - 1][j][3] + dp[v[i]][0]});
				dp2[i][j][1] = min({dp2[i][j][1], dp2[i - 1][j][3] + dp[v[i]][1], dp2[i - 1][j][0] + dp[v[i]][0]});
				dp2[i][j][2] = min({dp2[i][j][2], dp2[i - 1][j][2] + dp[v[i]][2], dp2[i - 1][j][1] + dp[v[i]][3]});
				dp2[i][j][3] = min({dp2[i][j][3], dp2[i - 1][j][2] + dp[v[i]][3]});
			}
		}
		
		ll ans = min({dp2[M][0][3], dp2[M][1][3], dp2[M][2][2], dp2[M][3][2], dp2[M][0][0], dp2[M][1][0]});
		
		vector<ll> x;
		for(int i = 1; i <= M; i++) x.push_back(v[i]);
		x.push_back(v[0]);
		v.swap(x);
		
		for(int i = 0; i <= M; i++){
			for(int j = 0; j < 4; j++){
				for(int k = 0; k < 4; k++) dp2[i][j][k] = INF;
			}
		}
		
		for(int i = 0; i < 4; i++) dp2[0][i][i] = dp[v[0]][i];

		for(int i = 1; i <= M; i++){
			for(int j = 0; j < 4; j++){
				// 0 -> biru belum ada pasangan
				// 1 -> biru sudah ada pasangan
				// 2 -> putih sudah ada pasangan
				// 3 -> putih belum ada pasangan
				dp2[i][j][0] = min({dp2[i][j][0], dp2[i - 1][j][3] + dp[v[i]][0]});
				dp2[i][j][1] = min({dp2[i][j][1], dp2[i - 1][j][3] + dp[v[i]][1], dp2[i - 1][j][0] + dp[v[i]][0]});
				dp2[i][j][2] = min({dp2[i][j][2], dp2[i - 1][j][2] + dp[v[i]][2], dp2[i - 1][j][1] + dp[v[i]][3]});
				dp2[i][j][3] = min({dp2[i][j][3], dp2[i - 1][j][2] + dp[v[i]][3]});
			}
		}
		
		// cout << dp2[M][3][1] << "\n";
		ans = min({ans, dp2[M][0][3], dp2[M][1][3], dp2[M][2][2], dp2[M][3][2], dp2[M][0][0], dp2[M][1][0]});
		
		if(ans >= INF) ans = -1;
		cout << ans << "\n";
	}
}

/*

*/

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