Submission #741260

#	Time	Username	Problem	Language	Result	Execution time	Memory
741260		Pichon5	Logičari (COCI21_logicari)	C++17	110 / 110	218 ms	33436 KiB

Main

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <sstream>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define jumanji ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define F first
#define S second
#define int long long
#define vi vector<int>
#define ll long long
using namespace std;
//fin endpoints of one edge in a cycle of an undirected graph
int A,B;
const int tam=1e5+100;
vi G[tam];
const int INF=2e9;
int dp[tam][2][2][2][2];
int padre[tam];
ll solve (ll v, bool col_me, bool col_padre, bool col_A, bool col_B)
{
	if (dp[v][col_me][col_padre][col_A][col_B] != -1) return dp[v][col_me][col_padre][col_A][col_B];
	if (v == A && col_me != col_A)  return dp[v][col_me][col_padre][col_A][col_B] = INF;
	if (v == B && col_me != col_B)  return dp[v][col_me][col_padre][col_A][col_B] = INF;
	if (v == B && col_A && col_padre) return dp[v][col_me][col_padre][col_A][col_B] = INF;
	bool boo = 0;
	if (col_padre) boo = 1;
	if (v == A && col_B) boo = 1;
	if (v == B && col_A) boo = 1;
	ll sum = (ll)col_me;
	for (ll to : G[v])
	{
		if (to == padre[v]) continue;
		sum += solve(to, 0, col_me, col_A, col_B);
	}
	ll val = INF;
	if (boo)
	{
		val = sum;
	}
	else
	{
		for (ll to : G[v])
		{
			if (to == padre[v]) continue;
			ll cur = sum - solve(to, 0, col_me, col_A, col_B) + solve(to, 1, col_me, col_A, col_B);
			val = min(val, cur);
		}
	}
	return dp[v][col_me][col_padre][col_A][col_B] = val;
}
 
//union find
int p[tam];
int _find(int x){
    if(x==p[x])return x;
    return p[x]=_find(p[x]);
}
void join(int x, int y){
    x=_find(x);
    y=_find(y);
    p[x]=y;
}
void dfs(int nodo, int p){
    padre[nodo]=p;
    for(auto v:G[nodo]){
        if(v==p)continue;
        dfs(v,nodo);
    }
}
 
signed main(){
    jumanji
    memset(dp,-1,sizeof dp);
    int n,a,b;
    cin>>n;
    for(int i=0;i<=n;i++)p[i]=i;
    for(int i=1;i<=n;i++){
        cin>>a>>b;
        if(_find(a)==_find(b)){
            A=a;
            B=b;
        }else{
            join(a,b);
            G[a].pb(b);
            G[b].pb(a);
        }
    }
    dfs(A,A);
    ll ans = INF;
	ans = min(ans, solve(A, 0, 0, 0, 0));
	ans = min(ans, solve(A, 1, 0, 1, 0));
	ans = min(ans, solve(A, 0, 0, 0, 1));
	ans = min(ans, solve(A, 1, 0, 1, 1));
    if(ans==INF)cout<<-1<<endl;
    else cout<<ans<<endl;
 
    return 0;
}  
//Guess i wont be comming to church on sunday

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