oj.uz

Submission #741257

# Submission time Handle Problem Language Result Execution time Memory
741257 2023-05-14T00:17:09 Z Pichon5 Logičari (COCI21_logicari) C++17
10 / 110
 222 ms 32796 KB 
#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=0;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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15316 KB Output is correct
2 Correct 7 ms 15180 KB Output is correct
3 Correct 7 ms 15156 KB Output is correct
4 Correct 7 ms 15216 KB Output is correct
5 Correct 204 ms 32796 KB Output is correct
6 Correct 197 ms 32556 KB Output is correct
7 Correct 211 ms 32672 KB Output is correct
8 Correct 222 ms 32652 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 15188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 15188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15316 KB Output is correct
2 Correct 7 ms 15180 KB Output is correct
3 Correct 7 ms 15156 KB Output is correct
4 Correct 7 ms 15216 KB Output is correct
5 Correct 204 ms 32796 KB Output is correct
6 Correct 197 ms 32556 KB Output is correct
7 Correct 211 ms 32672 KB Output is correct
8 Correct 222 ms 32652 KB Output is correct
9 Incorrect 7 ms 15188 KB Output isn't correct
10 Halted 0 ms 0 KB -