oj.uz

Submission #741260

# Submission time Handle Problem Language Result Execution time Memory
741260 2023-05-14T00:20:12 Z Pichon5 Logičari (COCI21_logicari) C++17
110 / 110
 218 ms 33436 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=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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Correct 8 ms 15148 KB Output is correct
3 Correct 7 ms 15148 KB Output is correct
4 Correct 6 ms 15188 KB Output is correct
5 Correct 218 ms 32404 KB Output is correct
6 Correct 196 ms 32408 KB Output is correct
7 Correct 182 ms 32408 KB Output is correct
8 Correct 197 ms 32460 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15188 KB Output is correct
2 Correct 7 ms 15284 KB Output is correct
3 Correct 7 ms 15188 KB Output is correct
4 Correct 7 ms 15212 KB Output is correct
5 Correct 6 ms 15188 KB Output is correct
6 Correct 9 ms 15180 KB Output is correct
7 Correct 9 ms 15216 KB Output is correct
8 Correct 7 ms 15216 KB Output is correct
9 Correct 6 ms 15188 KB Output is correct
10 Correct 7 ms 15216 KB Output is correct
11 Correct 7 ms 15112 KB Output is correct
12 Correct 7 ms 15216 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15188 KB Output is correct
2 Correct 7 ms 15284 KB Output is correct
3 Correct 7 ms 15188 KB Output is correct
4 Correct 7 ms 15212 KB Output is correct
5 Correct 6 ms 15188 KB Output is correct
6 Correct 9 ms 15180 KB Output is correct
7 Correct 9 ms 15216 KB Output is correct
8 Correct 7 ms 15216 KB Output is correct
9 Correct 6 ms 15188 KB Output is correct
10 Correct 7 ms 15216 KB Output is correct
11 Correct 7 ms 15112 KB Output is correct
12 Correct 7 ms 15216 KB Output is correct
13 Correct 8 ms 15216 KB Output is correct
14 Correct 8 ms 15188 KB Output is correct
15 Correct 7 ms 15216 KB Output is correct
16 Correct 8 ms 15188 KB Output is correct
17 Correct 7 ms 15188 KB Output is correct
18 Correct 8 ms 15168 KB Output is correct
19 Correct 7 ms 15144 KB Output is correct
20 Correct 7 ms 15188 KB Output is correct
21 Correct 7 ms 15260 KB Output is correct
22 Correct 10 ms 15188 KB Output is correct
23 Correct 7 ms 15344 KB Output is correct
24 Correct 8 ms 15444 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Correct 8 ms 15148 KB Output is correct
3 Correct 7 ms 15148 KB Output is correct
4 Correct 6 ms 15188 KB Output is correct
5 Correct 218 ms 32404 KB Output is correct
6 Correct 196 ms 32408 KB Output is correct
7 Correct 182 ms 32408 KB Output is correct
8 Correct 197 ms 32460 KB Output is correct
9 Correct 6 ms 15188 KB Output is correct
10 Correct 7 ms 15284 KB Output is correct
11 Correct 7 ms 15188 KB Output is correct
12 Correct 7 ms 15212 KB Output is correct
13 Correct 6 ms 15188 KB Output is correct
14 Correct 9 ms 15180 KB Output is correct
15 Correct 9 ms 15216 KB Output is correct
16 Correct 7 ms 15216 KB Output is correct
17 Correct 6 ms 15188 KB Output is correct
18 Correct 7 ms 15216 KB Output is correct
19 Correct 7 ms 15112 KB Output is correct
20 Correct 7 ms 15216 KB Output is correct
21 Correct 8 ms 15216 KB Output is correct
22 Correct 8 ms 15188 KB Output is correct
23 Correct 7 ms 15216 KB Output is correct
24 Correct 8 ms 15188 KB Output is correct
25 Correct 7 ms 15188 KB Output is correct
26 Correct 8 ms 15168 KB Output is correct
27 Correct 7 ms 15144 KB Output is correct
28 Correct 7 ms 15188 KB Output is correct
29 Correct 7 ms 15260 KB Output is correct
30 Correct 10 ms 15188 KB Output is correct
31 Correct 7 ms 15344 KB Output is correct
32 Correct 8 ms 15444 KB Output is correct
33 Correct 128 ms 21076 KB Output is correct
34 Correct 120 ms 20876 KB Output is correct
35 Correct 122 ms 20864 KB Output is correct
36 Correct 132 ms 20868 KB Output is correct
37 Correct 27 ms 16624 KB Output is correct
38 Correct 128 ms 20956 KB Output is correct
39 Correct 13 ms 15700 KB Output is correct
40 Correct 133 ms 20736 KB Output is correct
41 Correct 71 ms 21952 KB Output is correct
42 Correct 89 ms 21820 KB Output is correct
43 Correct 152 ms 33436 KB Output is correct
44 Correct 133 ms 27556 KB Output is correct