Submission #741253

#	Time	Username	Problem	Language	Result	Execution time	Memory
741253		Pichon5	Logičari (COCI21_logicari)	C++17	10 / 110	226 ms	32476 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;

vector<vi>G;
//fin endpoints of one edge in a cycle of an undirected graph
int A,B;
const int tam=1e5+100;
const int INF=1e9;
int dp[tam][2][2][2][2];
int padre[tam];
int f(int nodo, int c,int cP, int cA, int cB){
    if(dp[nodo][c][cP][cA][cB] != -1) return dp[nodo][c][cP][cA][cB];
    if(nodo==A && c!=cA)return dp[nodo][c][cP][cA][cB]=INF;
    if(nodo==B && c!=cB)return dp[nodo][c][cP][cA][cB]=INF;
    if(nodo==B && cA && cP)return dp[nodo][c][cP][cA][cB]=INF;
    bool ok=0;
    if(cP)ok=1;
    if(nodo==A && cB)ok=1;
    if(nodo==B && cA)ok=1;
    int sum=c;
    for(auto v:G[nodo]){
        if(v==padre[nodo])continue;
        sum+=f(v,0,c,cA,cB);
    }
    dp[nodo][c][cP][cA][cB]=INF;
    if(ok){
        dp[nodo][c][cP][cA][cB]=sum;
    }else{
        for(auto v:G[nodo]){
            if(v==padre[nodo])continue;
            dp[nodo][c][cP][cA][cB]=min(dp[nodo][c][cP][cA][cB],sum-f(v,0,c,cA,cB)+f(v,1,c,cA,cB));
        }
    }
    return dp[nodo][c][cP][cA][cB];
}

//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;

    vector<pair<int,int>>edges;
    G.resize(n+1);
    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,-1);
    ll res=INF;
    res=min(res,f(A,0,0,0,0));
    res=min(res,f(A,0,0,0,1));
    res=min(res,f(A,1,0,1,0));
    res=min(res,f(A,1,0,1,1));
    if(res>=INF)cout<<-1<<endl;
    else cout<<res<<endl;




    return 0;
}  
//Guess i wont be comming to church on sunday

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